Approximation Algorithms and Hardness for Strong Unique Games

The UNIQUE GAMES problem is a central problem in algorithms and complexity theory. Given an instance of UNIQUE GAMES, the STRONG UNIQUE GAMES problem asks to find the largest subset of vertices, such that the UNIQUE GAMES instance induced on them is completely satisfiable. In this work, we give new algorithmic and hardness results for the STRONG UNIQUE GAMES problem.

Given an instance with label set size $k$ where a set of $1 – \eps$ fraction of the vertices induce an instance that is completely satisfiable, our first algorithm produces a set of $1 – \tilde{O}(k^2 \eps \sqrt{\log n})$ fraction of the vertices such that the UNIQUE GAMES induced on them is completely satisfiable. In the same setting, our second algorithm produces a set of $1 – \tilde{O}{k^2} \sqrt{\eps \log d}$ (here $d$ is the largest vertex degree of the graph) fraction of the vertices such that the UNIQUE GAMES induced on them is completely satisfiable The technical core of our results is a new connection between STRONG UNIQUE GAMES and {\em small-set vertex-expansion} in graphs. Complementing this, assuming the Unique Games conjecture, we prove that there exists an absolute constant $C$ such that it is NP-hard to compute a set of size larger than $1 – C \sqrt{\eps \log k \log d}$ such that all the constraints induced on this set are satisfied.

For the UNIQUE GAMES problem, given an instance that has as assignment satisfying $1 – \eps$ fraction of the constraints, there is a polynomial time algorithm [Charikar, Makarychev, Makarychev – STOC 2006] that computes an assignment satisfying $1 – O(\sqrt{\eps \log k})$ fraction of the constraints; [Khot et al. – FOCS 2004] prove a matching (up to constant factors) Unique Games hardness. Therefore, our hardness results suggest that the STRONG UNIQUE GAMES problem might be harder to approximate than the UNIQUE GAMES problem.

Given an undirected graph $G = (V,E)$ the ODD CYCLE TRANSVERSAL problem asks to delete the least fraction of vertices to make the induced graph on the remaining vertices bipartite. As a corollary to our main algorithmic results, we obtain an algorithm that outputs a set $S$ such the graph induced on $V \setminus S$ is bipartite, and $|S|/n \leq O(\sqrt{\eps \log d})$ (here $d$ is the largest vertex degree and $\eps$ is the optimal fraction of vertices that need to be deleted). Assuming the Unique Games Conjecture, we prove a matching (up to constant factors) hardness.