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 ...
- 5,762
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 ...
3
votes
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.5k
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 ...
3
votes
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.
- 71
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 ...
- 513
3
votes
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.1k
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:...
- 50.8k
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 ...
- 10.2k
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 ...
- 824
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....
- 20.8k
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 ...
- 800
Only top scored, non community-wiki answers of a minimum length are eligible