### On a Cut-Matching Game for the Sparsest Cut Problem

**Authors:**

Khandekar, Rohit

Khot, Subhash A

Orecchia, Lorenzo

Vishnoi, Nisheeth K
**Technical Report Identifier:** EECS-2007-177
**December 22, 2007**

EECS-2007-177.pdf

**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*).