5
$\begingroup$

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?

$\endgroup$

2 Answers 2

5
$\begingroup$

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 showed 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 is 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 Williamson, has trivial gap, but despite that an optimal solution to the relaxation actually provides enough guidance to achieve a non-trivial approximation factor.

$\endgroup$
17
  • $\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$
    – Turbo
    Sep 30, 2013 at 16:52
  • $\begingroup$ Can we have a lower bound to $MaxCut$ from eignevalues? $\endgroup$
    – Turbo
    Sep 30, 2013 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$ Sep 30, 2013 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$
    – Turbo
    Sep 30, 2013 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$ Sep 30, 2013 at 17:19
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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