On a Cut-Matching Game for the Sparsest Cut Problem
Khot, Subhash A
Vishnoi, Nisheeth K
Technical Report Identifier: EECS-2007-177
December 22, 2007
Abstract: 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).