Integrality gaps studied for graph cuts in finite Abelian Cayley graphs
Integrality Gap Bounds for the Goemans-Linial SDP on Finite Abelian Cayley Graphs
Discrete MathematicsData Structures and Algorithms
Summary
The paper examines how well a certain mathematical method approximates the best way to split a network into parts with few connections between them, called the sparsest cut problem. The authors focus on a special type of graph made from groups called finite Abelian Cayley graphs and find cases where this method perfectly solves the problem. They also show how randomizing certain steps in the graph affects the approximation quality and give a general bound on its accuracy. Finally, they present examples where the method's gap between the solution and optimum is exactly 16 over 15, illustrating the limits of this approach.
uniform sparsest cut problemGoemans-Linial SDPfinite Abelian Cayley graphssecond normalized Laplacian eigenvalueFourier characterapproximation ratiointegrality gapsemidefinite programminggroup theorygraph partitioning
Authors
Georgios Stamoulis
Abstract
In the uniform sparsest cut problem we are asked to find a vertex set that cuts few edges relative to the number of vertex pairs it separates. The Goemans-Linial SDP coupled with the Arora-Rao-Vazirani rounding gives an $\mathcal{O}(\sqrt{\log n})$ approximation on arbitrary graphs on $n$ vertices. We study this relaxation on finite Abelian Cayley graphs. First we show that when the second normalized Laplacian eigenvalue of $G= \mathrm{Cayley}(Γ, S)$ is realized by a Fourier character with image size at most four then $λ_2(G)=\mathrm{SDP}_{\mathrm{GL}}(G)=ψ(G)$. Geometrically, a character maps the vertices onto a regular polygon where the squared chord distance satisfies the triangle inequalities exactly when the polygon has at most four vertices. Grouping equal character fibers gives a cyclic quotient where the optimal cut can be found exactly and so the relaxation is exact on finite Abelian Cayley graphs on groups of exponent at most four. Second, we replace each generator $s$ of $S$ by a uniformly random element of its cyclic subgroup (including identity). If $r_s$ is the order of $s$, we let $α(r_s)$ to be the average number of $\pm s$ steps needed to simulate such a move, and let $ρ(S)=\max_{s\in S}α(r_s)$ be its worst case. Full cyclic averaging eliminates character phases and choosing a nontrivial character $χ^*$ minimizing the auxiliary eigenvalue and taking $K=\mathrm{ker}χ^*$ gives \[ ψ(G)\leqψ_G(K)\leq\frac{q^*}{q^*-1} \cdotρ(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G)\leq 2ρ(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G), \] where $q^*=|χ^*(Γ)|$. If all generator orders are at most $R$, this is an $R/2$ approximation. Finally, we construct an infinite family of finite Abelian Cayley graphs with Goemans-Linial integrality gap exactly $16/15$.