Hot answers tagged

10 votes
Accepted

A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut

Let me see if I can clarify this, on a high level. Assume the UG instance is a bipartite graph $G = (V \cup W, E)$, bijections $\{\pi_e\}_{e \in E}$, where $\pi_e\colon \Sigma \to \Sigma$, and $|\...
user avatar
9 votes
Accepted

Max flow: either saturate an edge or avoids

This problem is NP-hard. Reduction from PARTITION: Given a set of numbers $S=\{x_1,\ldots,x_n\}$, construct the following flow network: $$V = \{s,v,t\}\cup \{x_1,\ldots,x_n\}$$ $$E = \{(s,x_i) | ...
user avatar
  • 9,348
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 ...
user avatar
  • 5,712
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 ...
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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.
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 ...
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 ...
user avatar
  • 10k
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 ...
user avatar
  • 824
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:...
user avatar
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....
user avatar
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 ...
user avatar
  • 740

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