On a Cut-Matching Game for the Sparsest Cut Problem
Rohit Khandekar, Subhash A. Khot, Lorenzo Orecchia and Nisheeth K. Vishnoi
EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2007-177
December 22, 2007
http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-177.pdf
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).
BibTeX citation:
@techreport{Khandekar:EECS-2007-177,
Author = {Khandekar, Rohit and Khot, Subhash A. and Orecchia, Lorenzo and Vishnoi, Nisheeth K.},
Title = {On a Cut-Matching Game for the Sparsest Cut Problem},
Institution = {EECS Department, University of California, Berkeley},
Year = {2007},
Month = {Dec},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-177.html},
Number = {UCB/EECS-2007-177}
}
EndNote citation:
%0 Report %A Khandekar, Rohit %A Khot, Subhash A. %A Orecchia, Lorenzo %A Vishnoi, Nisheeth K. %T On a Cut-Matching Game for the Sparsest Cut Problem %I EECS Department, University of California, Berkeley %D 2007 %8 December 22 %@ UCB/EECS-2007-177 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-177.html %F Khandekar:EECS-2007-177