Source-linked AI summary
Max Cut and the Smallest Eigenvalue
Luca Trevisan
TL;DR
The paper addresses the difficulty of obtaining useful upper bounds for Max Cut optima while designing approximation algorithms. It develops spectral-partitioning methods, including a more sophisticated variant for instances near 1/2, and reports approximation guarantees including a bound of at least .531.
Problem
Max Cut approximation is difficult because general graphs lack good upper-bound techniques for the optimum beyond semidefinite programming.
Method
The paper develops spectral partitioning algorithms whose analysis uses semidefinite-programming dual solutions, including a more sophisticated variant for Max CutGain instances near 1/2.
Results
The reported approximation bound is always at least .531, while the near-1/2 variant finds cuts exceeding uncut edges by a 1/exp(Ω(1/ε)) fraction of incident edges.
Takeaways & Limitations
A natural, easy-to-implement spectral algorithm performs non-trivially well for Max Cut, and the algorithm made at most one recursive call in the reported experiments.
Takeaways & Limitations
The authors state that the worst-case approximation ratio is unknown and believe the .531 bound is not tight.
Abstract
from arXiv · showhide
We describe a new approximation algorithm for Max Cut. Our algorithm runs in $\tilde O(n^2)$ time, where $n$ is the number of vertices, and achieves an approximation ratio of $.531$. On instances in which an optimal solution cuts a $1-ε$ fraction of edges, our algorithm finds a solution that cuts a $1-4\sqrtε + 8ε-o(1)$ fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a $1-ε$ fraction of edges, our spectral partitioning algorithm finds a set $S$ of vertices and a bipartition $L,R=S-L$ of $S$ such that at least a $1-O(\sqrt ε)$ fraction of the edges incident on $S$ have one endpoint in $L$ and one endpoint in $R$. (This can be seen as an analog of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, variant of spectral partitioning leads to an $\tilde O(n^3)$ time algorithm that cuts $1/2 + e^{-Ω(1/\eps)}$ fraction of edges in graphs in which the optimum is $1/2 + ε$.
1 Introduction
The paper addresses the difficulty of improving Max Cut beyond the 1/2 baseline without relying on SDP as an algorithmic primitive. It introduces spectral partitioning procedures that yield strong guarantees on nearly bipartite graphs and additional guarantees near the 1/2 regime.
- Max Cut seeks a vertex partition maximizing the weight fraction of edges crossing between the two sides.
- General graphs admit a simple 1/2 approximation, while known stronger guarantees rely on SDP-based methods or assumptions about computational hardness.
- The central challenge is obtaining useful upper bounds on the Max Cut optimum for general graphs using techniques other than SDP.
- The main spectral partitioning result finds a subset S and bipartition L,R whose internal crossing edges comprise at least a 1-O(√ε) fraction of edges incident on S when optimum cost is 1-ε.
- Recursively removing the identified vertices and restoring their partition yields a cut of at least 1-4√ε+8ε-o(1) fraction of edges, with the worst-case ratio at least .531.
- A more sophisticated spectral method handles instances with optimum 1/2+ε, producing a cut of 1/2+1/exp(Ω(1/ε)); the paper also extends this approach to certain quadratic programs.
2 Sparsification
The paper sparsifies the input graph by uniform or weight-proportional edge sampling while preserving every cut value within an additive error with high probability. This removes explicit dependence on the number of edges from the running time, at a small approximation loss.
- Sampling O(δ^-2|V|) edges with replacement preserves the cost of every cut within additive error δ with high probability.
- After sparsification, the algorithm’s dependence on |E| can be replaced by dependence on |V| with an arbitrarily small loss in approximation factor.
3 The Spectral Algorithm
The spectral algorithm extracts a signed subset of vertices from an eigenvector-related relaxation and converts it into a useful partial cut. Its analysis connects the spectral condition to a combinatorial bipartition through thresholding and randomized-process arguments.
- Theorem 1 returns y∈{−1,0,1}^V for graphs with Max Cut optimum at least 1-ε, and its guarantee is expressed through edges incident on the nonzero-coordinate set.
- The matrix formulation uses the weighted adjacency matrix A and diagonal degree matrix D, whose entries encode edge weights and weighted degrees.
- The proof first obtains a vector from an optimization problem equivalent to computing the smallest eigenvalue of D^-1/2AD^-1/2.
- Lemma 3 converts a vector satisfying a quadratic-form condition into a vector y∈{−1,0,1}^V in O(|E|+|V| log |V|) time.
- The 2-Thresholds Spectral Cut algorithm sorts coordinates by magnitude and tests threshold-based vectors, requiring O(|E|+|V| log |V|) time.
- Its analysis samples a random threshold and bounds expected edge contributions, using inequalities such as E|Y_i+Y_j|≤|x_i+x_j|(|x_i|+|x_j|).
4 Approximation for Max Cut
Recursive-Spectral-Cut repeatedly removes vertex subsets with nearly bipartite incident edges, then recurses on the residual graph. This yields a .531128−δ approximation and stronger guarantees when the optimum is close to one.
- Algorithm: The algorithm assigns vertices to L, R, or zero, recursively solves the induced zero-vertex graph, and combines the resulting partitions.It may instead return a greedy half-edge cut when the recursive instance is sufficiently small.
- Algorithm: The procedure runs in randomized time O(δ^-2 · |V| · (|V| + |E|) · log |V|).Each iteration takes O(δ^-1 · (|V| + |E|) · log |V|), with at most |V| iterations.
- Approximation guarantees: 1−4√ε guarantees are obtained when the optimum is 1−ε for ε < 1/16.The theorem states this bound for Recursive-Spectral-Cut; the displayed passage is completed by the accompanying result statement.
- Analysis: At each iteration, the residual graph’s optimum is at least 1−ε/ρ_t when it contains a ρ_t fraction of the original edges.The algorithm cuts a guaranteed fraction of edges incident on the selected subset, using at least one-half when the spectral bound is weaker.
- Approximation guarantees: .531128−δ is the approximation guarantee of Recursive-Spectral-Cut.For ε outside the near-perfect regime, the analysis combines the algorithm’s cost bounds and minimizes the resulting ratio to obtain .531128….
5 Relation to Cheeger’s Inequality
The paper presents its spectral partitioning result as an analog of Cheeger’s inequality for the smallest adjacency-matrix eigenvalue. Near −1, that eigenvalue corresponds to a subset whose incident edges are nearly all cut by a bipartition.
- Analogy: For a regular graph, the main result is framed as an analog of Cheeger’s inequality for the smallest rather than second-largest adjacency eigenvalue.The comparison is restricted to regular graphs.
- Spectral characterization: λ_n = −1 exactly when the graph has a bipartite connected component.Equivalently, some subset S can be partitioned into L and R so every incident edge crosses between them.
- Comparison with Cheeger: Cheeger’s inequality links λ_2 close to 1 with a set having few edges leaving it relative to its volume.The paper defines h(G) as edge expansion and states the corresponding inequality.
- Comparison with Cheeger: The analogous smallest-eigenvalue statement identifies λ_n close to −1 with a subset whose incident edges have few failures to cross the bipartition.Thus the relevant defect is uncut incident edges rather than boundary edges leaving the subset.
- Tightness: The two inequality directions are tight within constant factors, illustrated by odd cycles and constructed regular graphs.Odd cycles and the expander-plus-bipartite construction witness the two types of tightness.
- Proof analogy: The proof analogy uses quadratic forms: small values of the relevant form indicate edgewise similarity for ordinary Cheeger analysis and opposite-sign structure here.The paper’s form includes A(i,j)·(x_i + x_j)^2 for the smallest-eigenvalue setting.
6 Relation to the Goemans-Williamson Relaxation
The algorithm can be viewed as a primal-dual method for the Goemans-Williamson relaxation: it outputs both a cut and a feasible dual certificate. The certificate upper-bounds the optimum and supports the reported approximation guarantees.
- Dual interpretation: A feasible solution to the Goemans-Williamson dual provides an upper bound on the optimal cut.The paper uses weak duality to interpret the dual cost as an upper bound on Max Cut.
- Dual interpretation: If the optimum exceeds |E|·(1−ε), then a dual candidate of cost |E|·(1−ε) cannot be feasible.This infeasibility yields a vector witnessing that the associated matrix is not positive semidefinite.
- Primal-dual view: The recursive algorithm is a primal-dual algorithm that produces a cut together with a feasible semidefinite dual solution.At each recursive step, the dual solution supplies an upper bound for the original graph’s optimum.
- Guarantee: The algorithm cuts at least a 1−4√ε+8ε−δ/2 fraction of edges and produces a dual certificate proving an upper bound of 1−ε on the optimum.These two outputs are analyzed together to obtain the approximation ratio.
- Guarantee: .531 is the minimum ratio between the algorithm’s cut cost and the dual upper bound.The paper states that this ratio is always at least .531.
7 Quadratic Programming and the Max CutGain Problem
The section develops spectral and randomized-rounding methods for Max CutGain and related quadratic programs, including nearly quadratic- and nearly cubic-time algorithms with exponentially small guarantees in the inverse gain parameter.
- Max CutGain measures the difference between cut and uncut edges, normalized by the total number of edges; gain ε corresponds to Max Cut optimum 1/2 + ε.
- The gain ratio extends this objective to vertex subsets S and partitions (L, R), recovering Max CutGain when S = V.
- A (c1, c2, 1/ℓ)-good randomized rounding of any real vector exists with c1 · c2 ≤ ℓ^-1 · e^ℓ.
- Nearly linear-time threshold search and almost pairwise-independent sample spaces make the rounding procedure constructive.
- A nearly quadratic-time algorithm finds a subset and partition with gain at least e^-Ω(1/ε) when γ(G) ≥ ε.
- A nearly cubic-time iterative algorithm finds a full cut with gain at least e^-Ω(1/ε) when Max-Cut gain is at least ε.
8 Conclusions
The paper interprets the smallest eigenvalue through bipartiteness and shows that spectral partitioning performs non-trivially for Max Cut, while leaving several bounds and algorithmic questions open.
- The motivating question is a combinatorial interpretation of d − |λ_n| in d-regular graphs, analogous to edge expansion's interpretation of d − λ_2.
- The paper introduces a bipartiteness-ratio interpretation and obtains a natural, easy-to-implement spectral algorithm with non-trivial Max Cut performance.
- In experiments, a relaxed termination rule led the algorithm to make at most one recursive call, although the paper does not prove this always occurs.
- The authors believe the .531 worst-case approximation bound is not tight.
- Open questions include a purely combinatorial algorithm beating 1/2 for Max Cut and significantly improved Max CutGain bounds.
A.1 Efficiency of the Arora-Kale Algorithm
A randomized reduction transforms an arbitrary graph into a nearly linear-size bounded-degree graph, allowing Arora–Kale's near-linear Max Cut approximation to apply without degree-distribution restrictions.
- Arora–Kale provides near-linear-time approximation on bounded-degree multigraphs, achieving α −o(1) with α = .878 ···.Its running time is ˜O(Dmax · |V |) for an input graph of maximum degree Dmax.
- α −o(1) approximation is achievable in time ˜O(|V | + |E|) regardless of the degree distribution.The reduction combines sparsification with the Arora–Kale algorithm.
- The reduction constructs a bounded-degree graph G′ with 2|E| vertices and preserves Max Cut cost up to o(1) with high probability.Given any solution of cost c in G′, the reconstruction algorithm returns a solution of cost at least c −o(1) in G.
- The reduction analyzes an implicitly defined weighted graph ˆG with one copy of each vertex per incident edge and normalized complete bipartite edge expansions.For an edge (u, v), the construction uses du · dv copy-edges, each of weight 1/(du · dv).
- G′ is formed by sampling ˜O(|ˆV |) weighted edges from ˆG, and sampled solutions approximate their costs in ˆG within o(1).The sampling argument relies on Chernoff bounds.
- The reduction avoids explicit construction of ˆG because it can have Ω(|V |^2) edges even when the original graph is sparse.After preprocessing, edges of the implicit graph can instead be sampled in constant time.