# Tag Info

13

My earlier claim of $\frac{2}{c+6}$ did not take into account the cut of size $n^2/4$ already present in the graph. The following construction appears to result (emperically - I have created a question at math.stackexchange.com for a rigorous proof) in a $O\left(\frac{1}{\log c}\right)$ fraction. The algorithm performs badly on unions of several ...

12

After a while of thinking and asking around, here's a counter-example, courtesy of Ami Paz: Let $n$ be even and $G$ be a graph which is the union of $K_n$ with a matching of $n+2$ vertices (that is, a matching with $n/2+1$ edges). How does the algorithm run on this graph? It just takes vertices from the clique part in arbitrary order. After having taken $k$...

10

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 $|\Sigma| = m$. You want to construct a new graph $H$ so that if the UG instance is $1-\delta$ satisfiable, then $H$ has a large cut, and if the UG instance is not ...

9

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) | x_i\in S\} \cup \{(x_i,v)|x_i\in S\} \cup \{(v,t)\}$$ $$c((s,x_i))=c((x_i,v))=x_i\ \ \ c((v,t))=\frac{\sum_{i\in[n]}{x_i}}{2}$$ $S$ is partitionable iff there ...

5

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 Complexity" by C.H. Papadimitriou). The first proof goes back to the year 1976: M.R. Garey, D.S. Johnson, L. Stockmeyer Some simplified NP-complete graph problems ...

4

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 have 6 edges in a cut. By the following lemma the size of a maximal cut can not be much smaller. Lemma. In any undirected 4-regular with $n$ nodes there exists ...

4

Yes, there is a connection between the spectrum of the graph and the size of the maximum cut. It might be easiest to see this with the normalized graph Laplacian, $L = I - D^{-1/2}AD^{-1/2}$, where $I$ is the identity, $A$ is the adjacency matrix of the graph $G = ([n], E)$ and $D$ is the diagonal matrix defined by $D_{ii} = d_i$, the degree of vertex $i$. ...

4

After more thought, I found a simple approximation-preserving reduction from independent set, showing that this problem is hard to approximate better than $n^{0.5}$. Here it is. Consider a graph $G=(V,E)$ with n vertices. Construct the following matrices, with columns indexing the vertices. For each vertex $v$, construct a matrix with the top row ...

3

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 a random cut has size $|E|/2$ in expectation), and otherwise this problem can be solved in $O(2^{4k})$ rounds by enumerating over all possible cuts on vertices ...

3

Let's consider unweighted graphs, which is still a hard problem. Say you have an algorithm that solves your problem in time $T(n)$. Then I could solve the MAX CUT problem without such an oracle in time $O(m\cdot T(n))$, where $m$ is the number of edges in the graph. Run $m+1$ versions of your algorithm in parallel, each of which gets a different value for ...

3

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 for the problem and prove it's NP-hard. Charikar, Guruswami, and Wirth show the problem is APX-hard, and improve the approximation factor to 4 via region growing....

3

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

3

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 be no SDP relaxations for exact Max-CUT of size $2^{n^c}$ for some $c < 1$. I think this means there can be no SOS proof of degree $n^c$, and hence there ...

2

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 function to edges whose endpoints that are placed farther apart in the vector solution, so it makes sense to cluster the set of vertices geometrically into two ...

2

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 it to your instance after taking the opposite weights and looking whether the result is positive seems to solve your problem.

2

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:10.1016/j.dam.2004.01.007, "Efficient Parameterized Preprocessing for Cluster Editing", Michael Fellows, Michael Langston, Frances Rosamond, and Peter Shaw, ...

2

Yes. The original Goemans-Williamson paper also discusses the dual of the PSD relaxation, which is equivalent to minimizing $\lambda_{max}(L_G+D)$, over all the traceless diagonal matrices D. Trevisan used some of this intuition to design a nontrivial approximation to MaxCut, at the bottom of which lies a spectral partitioning algorithm. In his algorithm, ...

2

Yes. You could find the actual cut using $n$ calls to the oracle. Let the vertices be labeled $1, \dots, n$. Add a dummy vertex $0$ with outgoing edge weights equal to zero. For each vertex $j=2,\dots, n$ tentatively merge $j$ with vertex $1$. If the max cut objective remains the same, leave $j$ and 1 merged. Otherwise, merge $j$ with $0$ instead.

1

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 0$ for every $x\in \{-1,1\}^n$. As you write, it is trivially true that $c^*=\mathsf{OPT}(G)$ is the optimal value where this holds by definition, but for one, ...

1

This is perhaps not entirely satisfactory since you asked for an approximation rather than a hardness result but there is no constant independent of $a$ for which the problem can be approximated to within via an FGLSS-like reduction. Unless P=NP, for every $\epsilon > 0$, there exists $c_0$ such that there is no poly-time $\epsilon$-approximation for ...

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