We study the following game between a "cut" player C and a "matching" player M. The game starts with an empty graph G on a set V of n vertices. In each round, the cut player chooses a bisection (S,V\S) of vertices and the matching player then adds a perfect matching M (not necessarily belonging to G) between S and V\S to the (multi-)graph G. The choices of the players in each round may depend on those in the previous rounds. The game ends when G becomes an edge-expander. The value of this game, denoted by Val(n,C,M), is the total number of rounds in the game before it ends. We study this game for its connection with the Sparsest Cut problem in undirected graphs: if there is a polynomial-time cut player C such that Val(n,C,M) < f(n) for all M, then there is a polynomial-time O(f(n))-approximation algorithm for the Sparsest Cut problem.
We show that there is no cut player C, even unbounded-time, that can ensure Val(n,C,M) = o(GAP(n)^1/2) for all matching players M, where GAP(n) is the integrality gap of the well-studied SDP with triangle inequality constraints for the Sparsest Cut problem. Recall that GAP(n) = Omega(log log n). Thus, we prove that this approach cannot yield a o(GAP(n)^1/2)-approximation (and in particular, o((log log n)^1/2)-approximation) algorithm for this problem. Furthermore, we show that there is a (super-polynomial time) cut player C* such that, for all M, we have Val(n,C*,M) = O(log n).
On a Cut-Matching Game for the Sparsest Cut Problem
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).