### 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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-177.html}, Number = {UCB/EECS-2007-177}, 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)<SUP>1/2</SUP>) 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)<SUP>1/2</SUP>)-approximation (and in particular, o((log log n)<SUP>1/2</SUP>)-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).} }

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://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-177.html %F Khandekar:EECS-2007-177