Is there an interpretation of MAXCUT using eigenvalues of the graph that yields constant factor approximation to MAXCUT?

Can the estimates provide sharp lower bound to MAXCUT?


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$. The largest eigenvalue of $L$ is

$$\lambda_{n-1} = \max_x\frac{x^TLx}{x^Tx} = \max_{x}\frac{\sum_{(i, j) \in E}{(x_i - x_j)^2}}{\sum_{i}{d_i x_i^2}}.$$

Because $(x_i - x_j)^2 \leq 2x_i^2 + 2x_j^2$ by Cauchy-Schwarz, $\lambda_{n-1} \leq 2$. Equality is achieved if and only if for each edge $(i, j)$, $x_i = -x_j$, which means that $\lambda_{n-1}= 2$ only if the graph has a bipartite connected component, i.e. a connected component whose maximum cut is equal to the number of edges in the component.

For a robust version of this result, see Luca Trevisan's paper. He shows that

$$ \lambda_{n-1} \geq 2\frac{\text{MaxCut}}{m}, $$

(where $m$ is the number of edges of the graph) and if $\lambda_{n-1} \geq 2(1-\epsilon)$, then there exits a set of vertices $S$ and a partition $(S_1, S_2)$ of $S$ such that

$$ |e(S_1, S_2)| \geq \frac{1}{2}(1-\sqrt{16\epsilon})\text{vol}(S), $$ where $\text{vol}(S) = \sum_{i \in S}{d_i}$ and $e(S_1, S_2)$ is the set of edges with one endpoint in $S_1$ and the other in $S_2$.

Note that the second bound does not necessarily lower bound the max cut in a useful way: it only lower bounds the maximum cut of the set $S$ in terms of $\text{vol}(S)$. This is unavoidable: think of a graph that's the disjoint union of an edge and a large graph with small maximum cut, say a clique. The maximum cut of the graph is very close to $m/2$, which is the minimum possible value of the max cut of a graph with $m$ edges. However, $\lambda_{n-1} = 2$, the maximum possible value of $\lambda_{n-1}$. In other words, while $\lambda_{n-1}$ is a relaxation of the maximum cut (up to appropriate rescaling), the gap is arbitrarily close to 2, and a 2-approximation to max cut is trivial.

Nevertheless, in the paper Luca uses the spectral result to design a recursive approximation algorithm for max cut. This is one cool thing about the paper: it uses a relaxation that, unlike the SDP relaxation of Goemans and Wiliamson, has trivial gap, but despite that an optimal solution to the relaxation actually provides enough guidance to achieve a non-trivial approximation factor.

  • $\begingroup$ Thankyou. What is $m$? what is $e(S_1,S_2)$ here? And so we have $MaxCut \leq \frac{\lambda_{n-1}}{2m}$? $\endgroup$ – 1.. Sep 30 '13 at 16:52
  • $\begingroup$ Can we have a lower bound to $MaxCut$ from eignevalues? $\endgroup$ – 1.. Sep 30 '13 at 16:56
  • 1
    $\begingroup$ I think you did the algebra wrong there, the max cut is at most $m \lambda_{n-1}/2$. This is the easy direction however. Indeed, the second bound is a partial converse. Note that it only says something about the subset $S$, however. In general you cannot lower bound the maximum cut of the entire graph from $\lambda_{n-1}$ because it's possible to have $\lambda_{n-1} = 2$ but the maximum cut being arbitrarily close to its minimum possible value, $m/2$ $\endgroup$ – Sasho Nikolov Sep 30 '13 at 17:01
  • $\begingroup$ I see that $MaxCut*d_{max}\geq|e(S_1,S_2)|$ and hence $MaxCut\geq\frac{1}{2d_{max}}(1-\sqrt{16\epsilon})Vol(S)$. Is this a sharp lower bound? However there is no eigenvalue here. $\endgroup$ – 1.. Sep 30 '13 at 17:02
  • 1
    $\begingroup$ So the bad example is quite robust. It's not necessary to have a bipartite connected component: just a small set of vertices that induce a subgraph which is close to bipartite and the cut between these vertices and the rest of the graph is small. $\endgroup$ – Sasho Nikolov Sep 30 '13 at 17:19

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, he essentially looks at the largest eigenvector of the normalized Laplacian in order to isolate components of the graph between which there is a large cut. The core of the analysis is a Cheeger-like inequality for the largest eigenvalue.

  • $\begingroup$ "....all traceless" contains complex matrices? $\endgroup$ – 1.. Sep 30 '13 at 16:54
  • $\begingroup$ No, we're only looking at real matrices. $\endgroup$ – zotachidil Sep 30 '13 at 17:32
  • $\begingroup$ I think since L is real, D the optimal D will be real wlog $\endgroup$ – Sasho Nikolov Sep 30 '13 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.