Skip to main content
Share Your Experience: Take the 2024 Developer Survey
5 votes

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 ...
Gamow's user avatar
  • 5,772
4 votes

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 ...
Sasha Kozachinskiy's user avatar
3 votes

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 ...
Jukka Suomela's user avatar
3 votes

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 ...
user3209423940248's user avatar
3 votes

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.
allrtaken's user avatar
3 votes

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 ...
Whosyourjay's user avatar
3 votes

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 ...
Sasho Nikolov's user avatar
2 votes

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:...
David Eppstein's user avatar
2 votes

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 ...
Aryeh's user avatar
  • 10.6k
2 votes

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 ...
Arnaud's user avatar
  • 834
2 votes

Deciding if max-cut with negative edge weights has a solution with positive value

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 $\...
Neal Young's user avatar
  • 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....
Mohammad Al-Turkistany's user avatar
1 vote

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 ...
Jason Gaitonde's user avatar

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