Share Your Experience: Take the 2024 Developer Survey

# Tag Info

### Is the max cut problem still NP-Complete for graphs with unit weights on the edges?

Yes, Max-Cut is still NP-complete in unweighted graphs. This is explained in pretty much every survey article on tthe Max-Cut problem, and in many texbooks (as for instance "Computational ...
• 5,772

### MaxCut instance with smallest max cut

Take a clique of size 5 and consider a graph on $n = 5k$ nodes consisting of $k$ copies of this clique. The size of a maximal cut in this graph is $6k = 6n/5$. Indeed, from each copy we can maximally ...
Accepted

### State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson

These are not directly comparable: Goemans–Williamson and related work: find a cut in any graph G [of some graph family] that is at least X times the size of the maximum cut of G. This is the usual ...
• 11.6k

### Partition vertices of graph into two sets such that there are at least $k$ edges between sets

Is $k$ considered a constant in this context? If so, the problem can be trivially solved in linear time. If $|E| \geq 2k$ then the answer is yes (there is always a cut of size at least $|E|/2$, since ...
Accepted

### Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

The problem of bipartite exact cuts is NP-Complete, as shown here by a reduction from exact cuts in general graphs.

### SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?

We don't have integrality gaps even for Max-CUT, even for degree 4. See Barak and Steurer's notes, at the end. You might be interested in Lee Raghavendra Steurer '14. They seem to be saying there can ...
• 513
Accepted

### Name of graph partition that balances edges between sets with edges remaining within sets

This is the Min-Disagreements version of the correlation clustering problem (on complete graphs), defined by Bansal, Blum, and Chawla (full version). They give a (huge) constant factor approximation ...
• 18.2k

### Name of graph partition that balances edges between sets with edges remaining within sets

In the parameterized complexity community, it is called cluster editing. See e.g. "Cluster graph modification problems", Ron Shamir, Roded Sharan and Dekel Tsur, Discrete Applied Mathematics 2004, doi:...

### Intuitive explanation behind Goemans-Williamson randomized rounding

Great intuitive explanations above by Sasho Nikolov and Neal Young. Here's another one Eden Chlamtáč emailed in: Well, the intuition is that the SDP solution assigns greater weight in the objective ...
• 10.6k

### Weighted Min-Cut in bounded-genus graphs

For graphs embedded on a surface of genus g with bounded weights $w:E \rightarrow \mathbb{Z}$, you can solve MAX-CUT in time $4^g poly(n)$ using an algorithm of Gallucio, Loebl and Vondrák. Applying ...
• 834
Accepted

Lemma 1. The problem is strongly NP-hard. Proof. The proof is by reduction from the NP-hard Sparsest Cut problem. For this problem, the input is a connected undirected graph $G=(V, E)$ and a budget $\... • 10.8k 1 vote ### Minimum cut with size bounds$k\leq |S| \leq |V|-k$The NP-complete Balanced min cut problem ($|S|< c|V|$and$|V-S|<c|V|$for$0<c<1$) is a special case of your problem. Hence your problem is NP-complete. Reference: Garey, M.R., Johnson, D.... 1 vote Accepted ### Sum-of-Squares Certificates I see the confusion, but I think the document you provided pretty well explains what is meant: solving MAXCUT on a graph$G$is equivalent to finding the smallest value of$c$such that$c-f_G(x)\geq ...

Only top scored, non community-wiki answers of a minimum length are eligible