Plaintext
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128
http://theoryofcomputing.org
Approximation Algorithms
for Unique Games∗
Luca Trevisan†
Received: May 11, 2008; published: October 10, 2008.
Abstract: A unique game is a type of constraint satisfaction problem with two variables
per constraint. The value of a unique game is the fraction of the constraints satisfied by an
optimal solution. Khot (STOC’02) conjectured that for arbitrarily small γ, ε > 0 it is NP-
hard to distinguish games of value smaller than γ from games of value larger than 1 − ε.
Several recent inapproximability results rely on Khot’s conjecture.
Considering the case of sub-constant ε, Khot (STOC’02) analyzes an algorithm based
on semidefinite programming that satisfies a constant fraction of the constraints in unique
games of value 1 − O(k−10 · (log k)−5 ), where k is the size of the domain of the variables.
We present a polynomial time algorithm based on semidefinite programming that, given
a unique game of value 1−O(1/ log n), satisfies a constant fraction of the constraints, where
n is the number of variables. This is an improvement over Khot’s algorithm if the domain
is sufficiently large.
∗ An extended abstract of this paper appeared in the Proceedings of the 46th Annual IEEE Symposium on Foundations of
Computer Science (FOCS 2005), pages 197–205.
† This material is based upon work supported by the National Science Foundation under grant No. CCF 0515231 and by
the BSF under grant 2002246.
ACM Classification: F.2.2
AMS Classification: 68Q17
Key words and phrases: complexity theory, approximation algorithms, constraint satisfaction, unique
games
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2008 Luca Trevisan DOI: 10.4086/toc.2008.v004a005
L UCA T REVISAN
We also present a simpler algorithm for the special case of unique games with linear
constraints, and a simple approximation algorithm for the more general class of 2-to-1
games.
1 Introduction
A unique game [8] is described by a set V of variables, taking values over a finite set S (we will refer to
S as the alphabet of the games), and a collection of constraints of the form
v = f (u)
where u, v ∈ V are variables and f : S → S is a permutation. We are interested in finding the assignment
A : V → S to the variables that satisfies the largest number of constraints. The value of a unique game is
the fraction of the constraints satisfied by an optimal assignment. For example, the following is a unique
game with V = {v1 , v2 , v3 , v4 } and S = {a, b, c}:
abc
v3 = (v1 )
cba
abc
v3 = (v2 )
acb
v1 = v2
abc
v4 = (v2 )
bca
Here we used the notation ax by zc to represent the permutation f such that f (a) = x, f (b) = y and
f (c) = z. Such a system of constraints is unsatisfiable (in particular, it is impossible to simultane-
ously satisfy the first three constraints), but the assignment (v1 , v2 , v3 , v4 ) = (c, a, a, b) satisfies three
constraints. The value of the game, therefore, is 3/4.
We will adopt the convention that if v = f (u) is a constraint, then v > u in lexicographic order, a
convention that is made with no loss of generality because the constraint u = g(v) with u < v is equivalent
to v = g−1 (u). We allow the same pair of variables to occur in more than one constraint.
The constraint graph of a unique game is the graph G = (V, E) where V is the set of variables and
there is an edge e = (u, v) in E for every constraint v = f (u). If the same two variables occur in multiple
constraints, then G is a graph with parallel edges.
Formally, a unique game is a triple (G = (V, E), { fe }e∈E , S) where G is the constraint graph, S is the
range of the variables, and for every edge e ∈ E, e = (u, v), v > u, we have the constraint v = fv,u (u). We
−1 .
also define the permutation fu,v , v > u, as fu,v := fv,u
Given a unique game, if there exists an assignment that satisfies all constraints then it is easy to find
such an assignment, as follows. One may assume without loss of generality that the graph is connected
(otherwise, apply the following algorithm to each connected component), and so one can find a spanning
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 112
A PPROXIMATION A LGORITHMS FOR U NIQUE G AMES
tree. Fix a satisfying assignment A for the unique game; guess the value A(r), where r is the root of the
spanning tree, and then find A(v) for every other vertex v, by noting that
A(v) = fv,uk ( fuk ,uk−1 (· · · ( fu2 ,u1 ( fu1 ,r (A(r)))) · · · ))
where r, u1 , . . . , uk , v is the path from r to v in the spanning tree.
If one is given an almost satisfiable unique game, that is, a game admitting an assignment that
satisfies a 1 − γ fraction of the constraints for some small γ, then no efficient algorithm is known to find
a good assignment, that is, say, an assignment that satisfies a constant fraction of constraint independent
of γ. Khot’s [11] Unique Games Conjecture is that for every 0 < γ < 1/2 there is a constant c = c(γ)
such that it is NP-hard to distinguish games of value ≥ 1 − γ from games of value ≤ γ, even when
restricted to alphabets of size c and to graphs that are bipartite.1
The Unique Games Conjecture has been shown to imply several inapproximability results, such as
that the minimum edge-deletion bipartite subgraph problem is hard to approximate within any constant
factor [11], that the Vertex Cover problem is hard to approximate within 2 − ε for every ε > 0 [14],
that the Max Cut problem is hard to approximate within .878 · · · [12, 18], and that the Sparsest Cut
problem [5] is hard to approximate within any constant. Extensions of the Unique Games Conjecture
to subconstant γ have been used to prove that the Sparsest Cut problem is hard to approximate within
Ω((log log n)1/6 ) [15]. Several recent papers [23, 13, 2, 3, 20, 21, 17], too many to describe individually,
have established inapproximability results for constraint satisfaction problems and other optimization
problems by relying on the Unique Games Conjecture.
In partial support of this conjecture, Feige and Reichman [9] prove that it is NP-hard (under quasi-
.99
polynomial time reductions) to approximate the value of a unique game within a factor 2(log n) . The
value of the instances produced by their reduction, however, is very small, and so their result does not
show that it is hard to distinguish instances of value 1 − γ from instances of value γ.
Given that there are now several results, including [11, 14, 12, 18, 15, 5, 23, 13, 2, 3, 20, 21, 17],
based on the Unique Games Conjecture, there is a good motivation to investigate algorithms that might
contradict it. Prior to our work, the main algorithmic result on unique games was due to Khot [11],
who presents an algorithm that given a unique game with an alphabet of size k and the promise that a
1 − O(ε 5 /k10 (log k)5 ) fraction of the constraints is satisfiable, finds an assignment that satisfies a 1 − ε
fraction of the constraints.
Khot [11] also introduces 2-to-1 games. In general, for integers d, d 0 a d-to-d 0 game is defined by a
set of variables V ranging over a set S, and a set of constraints of the form
P(u, v) = 1
where u, v ∈ V are variables and P : S × S → {0, 1} is a d-to-d 0 predicate, that is, a predicate such that
for every a ∈ S there are at most d 0 values b such that P(a, b) = 1, and for every b ∈ S there are at most
d values a such that P(a, b) = 1. As before, we want to find an assignment A : V → S to the variables
that maximizes the number of satisfied constraints. The value of a d-to-d 0 game is the fraction of the
constraints satisfied by an optimal assignment. We will restrict ourselves to the case d = d 0 , which is
1 Unique games on general graphs can be reduced to unique games on bipartite graphs, so the restriction to bipartite graphs
is done with no loss of generality.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 113
L UCA T REVISAN
done without loss of generality. In a d-to-d game we will follow the convention that if P(u, v) = 1 is a
constraint then v > u. As before, the constraint graph of a game is a graph G = (V, E) where V is the set
of variables and E contains an undirected edge for every constraint. A d-to-d game is formally specified
by a triple (G = (V, E), {Pe }, S) where Pe : S × S → {0, 1} are d-to-d predicates.2
An example of a 2-to-2 game is the 3-coloring problem. If G is a graph, consider the 2-to-2 game
(G = (V, E), {neqe }e∈E , {a, b, c}), where the predicate neqe (x, y) is satisfied if and only if x 6= y. Then
assignments correspond to 3-colorings, and the game has value one if and only if the graph is 3-colorable.
Khot [11] conjectures that for every γ > 0 there is an alphabet S of size depending only on γ such
that it is hard to distinguish satisfiable 2-to-1 games (that is, games of value 1) from games of value
≤ γ, even if the games are restricted to use the fixed alphabet S. This conjecture has been shown to
imply intractability results for graph coloring [7]; as far as we know, there was no previous algorithmic
investigation on its validity.
A preliminary version of this article appeared in FOCS 2005. The version that appeared in FOCS
included an additional algorithm not described here; in this paper we provide the full proofs involved in
the analysis of the other algorithms.
1.1 Our results
In this paper we rule out a generalization of the Unique Games Conjecture to the case of subconstant γ
that could have been considered plausible given the result of Feige and Reichman [9].
Theorem 1.1. There is a constant c and an algorithm that, on input a unique game (G = (V, E), { fe }, S),
a parameter ε, and the promise that there is an assignment that satisfies a
c · ε3
1−
log |E|
fraction of the constraints, returns an assignment that satisfies at least a 1 − ε fraction of the constraints.
Furthermore, there is an algorithm that given the promise that the input unique game has value at least
1 − ε, finds an assignment that satisfies at least a 1/nO(ε) fraction of the constraints. The algorithms run
in time polynomial in |E| and |S|.
The algorithm of Theorem 1.1, described in Section 3, works by solving and then rounding a
semidefinite programming (SDP) relaxation of the unique game.
The restricted class of linear unique games has also been considered in the literature. Examples of
linear unique games are those in which every constraint is a linear equation over a finite field, or an
equation of the form x = y + a where the variables x, y range over a finite group. More generally, we call
a unique game linear if the permutations occurring in the instance generate a group of permutations in
which every permutation other than the identity has at most one fixed point.
We have a stronger result, derived from a simpler algorithm, for linear unique games.
2 The definition of 2-to-1 game given in [11] is slightly different, and the one given here is more general. Since we are
looking for algorithms, the additional generality in the definition only makes our results stronger.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 114
A PPROXIMATION A LGORITHMS FOR U NIQUE G AMES
Theorem 1.2. There is a constant c and an algorithm that, on input a linear unique game (G =
(V, E), { fe }, S), a parameter ε, and the promise that there is an assignment that satisfies a
c · ε2
1−
log |E|
fraction of the constraints, returns an assignment that satisfies at least a 1 − ε fraction of the con-
straints. Furthermore, there is a constant c0 and an algorithm that, on input a linear unique game
(G = (V, E), { fe }, S), and the promise that there is an assignment that satisfies a
c0 · (log log |E|)
1−
log |E|
fraction of the constraints, returns an assignment that satisfies at least a
c0 · (log log |E|)
log |E|
fraction of the constraints. The algorithms work in time polynomial in |E| and (assuming an efficient
representation of the group of permutations) log |S|.
For 2-to-1 games we are able to prove a weaker result, although our algorithm is sufficient to rule out
the type of hardness result that is known for general 2-variable constraint satisfaction problems [22], for
which it is NP-hard (under quasi-polynomial time reductions) to distinguish satisfiable instances from
.99
instances of value smaller than 1/2(log n) . Our algorithm also works for d-to-d games for large (even
super-constant) d.
Theorem 1.3. There is an algorithm that, on input a satisfiable d-to-d game (G = (V, E), {Pe }, S) returns
an assignment that satisfies at least a
√
1/2O( log |E|·log d)
fraction of the constraints. The algorithm runs in time polynomial in |E| and |S|.
In particular, Theorem 1.3 implies that for every satisfiable d-to-d 0 game we can satisfy at least a
√ 0
1/2O( log |E|·log max{d,d })
fraction of the constraints.
1.2 Overview of the algorithms
Our results all share the same general structure: (i) we first study “nice” instances where the constraint
graph has low diameter; and (ii) we show how to reduce general instances to nice ones, via a result of
Leighton and Rao [16] that gives a decomposition of general graphs into low-diameter components.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 115
L UCA T REVISAN
SDP-based algorithm for general unique games
Our approximation algorithm for general unique games is based on a semidefinite programming (SDP)
relaxation of unique games. In our analysis, we first present a rounding scheme that works well in
instances where the constraint graph has small diameter and where every edge gives a large contribution
to the objective function. We then give a reduction from the general case to such instances.
Our main result is a rounding algorithm with the following guarantee: given a solution for the SDP
such that every edge contributes at least 1 − δ to the objective function, and assuming that the constraint
graph has diameter d, we can find in polynomial time a solution that satisfies at least a 1−O(dδ ) fraction
of the constraints.
Given a general unique game of cost 1 − ε 3 / log n, we first remove all edges that contribute less than
ε 2 / log n to the objective function. By Markov’s inequality, this step removes at most an ε fraction of the
edges. Then we use a decomposition procedure by Leigthon and Rao that shows how to decompose a
graph in components of diameter d = O(ε −1 log n) by removing only an ε fraction of the edges. Finally,
we apply our rounding procedure to each component, thus satisfying at least a 1 − O(d · ε 2 / log n) =
1 − O(ε) fraction of the edges in each component. Overall, we have satisfied at least a 1 − O(ε) fraction
of the edges.
Algorithm for linear unique games
In the case of linear unique games, our main (and simple) technical lemma is that if the constraint graph
has diameter d, then we can either find an assignment that satisfies all edges, or we can find a set of at
most 4d + 2 constraints that cannot be simultaneously satisfied.
With this preliminary result in place, our algorithm works as follows: first, using the algorithm of
Leighton and Rao, it computes a decomposition of the graph such that, after removing at most an ε
fraction of the edges, every connected component has diameter O(log n). Then we try to satisfy all the
constraints of the residual graph, by applying our lemma to each connected component. Our lemma
guarantees that either we satisfy all constraints within all components, or we find an inconsistent set
of at most O(log n) constraints. In the former case, we stop; in the latter case we remove the O(log n)
inconsistent constraints from the graph, we re-compute a Leighton-Rao decomposition, and continue.
Our analysis of the algorithm relies on the fact that if the algorithm runs through T phases before
stopping, then it has found a collection of O(T log n) constraints such that every assignment contradicts
at least T of them. If we started from the promise that there is an assignment that satisfies at least
a 1 − O(ε/ log n) fraction of the constraints, then the algorithm must halt within T = O(ε · |E|/ log n)
steps, and hence it removes at most O(ε · |E|) constraints, before converging on a sub-instance that can
be completely satisfied.
Algorithm for 2-to-1 games
For 2-to-1 games our main result is that if we have a satisfiable instance in which the constraint graph
has diameter t, then it is possible to efficiently satisfy at least a 1/2t fraction of the constraints.
Our algorithm considers a spanning tree of diameter t of the constraint graph, guesses the value A(r)
of a satisfying assignment at the root, and then, for every vertex u, compiles a list Lu ⊆ S of values that
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 116
A PPROXIMATION A LGORITHMS FOR U NIQUE G AMES
are compatible with r having value A(r). For a vertex at distance i from r, the size of the list is at most
2i , and so for every vertex u the size of Lu is at most 2t . The algorithm then, for every vertex u, picks at
random an assignment from Lu : we see that every constraint is satisfied with probability at least 1/22t ,
and so on average at least a 1/22t fraction of the constraints is satisfied.
To apply our algorithm to general instances, we first use the Leighton-Rao algorithm to find a low
diameter decomposition of the constraint graph such that each
√ √ component has diameter at most t =
O( log n). This can be done by removing at most a 1 − 1/2O( log n) fraction of the edges.
Having started from a satisfiable instance, each component
√ in the decomposition is still satisfiable,
and so our algorithm will satisfy at least a 1/22t = 1/2O( log n) fraction of the constraints in each con-
nected component.
If we have a d-to-d game, a generalization of the algorithm described above can satisfy a 1/d 2t frac-
tion of the constraints
p in an instance of diameter t. In general instances, we first find a decomposition
√ of
−1
diameter k = O( log n · (log d) ), which can be done after removing at most a 1 − 1/2 log n·log d frac-
√
tion of the edges, and then our algorithm will satisfy at least a 1/2O( log n·log d) fraction of the constraints
in each component.
1.3 Weighted version of the problem
Recall that we allow multiple constraints to involve the same pair of variables, and so we allow the
constraint graph to have multiple edges.
When we refer to the degree of a vertex, we mean the number of edges incident on the vertex,
counting multiplicities. Similarly, we count multiplicities when we refer to the number of edges crossing
a cut in a graph, or to the number of edges in an induced subgraph, and so on.
The weighted version of the problem, where each constraint is allowed to have an arbitrary weight,
can be reduced to the unweighted version we consider in this paper by using a standard scaling and
rounding approximation-preserving reduction.
Standard sparsification techniques could also be used to reduce to the case |E| = |V | · (log |V |)O(1) ,
so that the dependencies of the quality of the approximation on |E| could be replaced by analogous
dependencies on |V |.
1.4 Later results
A number of new algorithmic results for unique games have been discovered since the initial announce-
ment of our results.
Gupta and Talwar [10] present an algorithm that, given a unique game of value 1 − ε, satisfies a
1 − O(ε log n) fraction of the constraints, that is, they are able to approximate the problem of minimizing
the number of contradicted constraints within a O(log n) factor. Their algorithm is based on linear
programming.
Charikar, Makarychev, and Makarychev [4] devise an improved SDP-based approximation algorithm
for unique games. Given a unique game of value 1 − ε, their algorithm satisfies a 1/|S|O(ε) fraction of
the constraints. In particular, their algorithm satisfies a constant fraction of the constraints in a unique
game of value 1 − O(1/ log |S|).
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 117
L UCA T REVISAN
In an instance of value 1 − ε, our algorithm only satisfies a 1/nO(ε) fraction of the constraints. In
the interesting case |S| = O(log n), the approximation 1/|S|O(ε) of the algorithm of Charikar et al. is
exponentially better.
Chlamtac, Makarychev and Makarychev [6] present an alternative SDP-based approximation algo-
√
rithm that satisfies a 1 − O(ε log n · log k) fraction of the constraints in a unique game of value 1 − ε.
Arora et al. [1] shows that if the constraint graph of a given unique game is an expander, then
applying our rounding strategy to an SDP solution of cost 1 − ε satisfies a 1 − O(ε) fraction of the
constraints. Their result contradicts the restriction of the Unique Games Conjecture to instances for
which the constraint graph is expanding.
2 Preliminaries
2.1 The Leighton-Rao graph decomposition
We say that a graph G = (V, E) has diameter at most d if every two vertices are connected by a path of
length at most d.
The following result is due to Leighton and Rao [16] and is used in several places in this paper.
Lemma 2.1 (Leighton and Rao [16]). There is a polynomial time algorithm that, on input a graph
G = (V, E) and a parameter t > 1, returns a subset of edges E 0 ⊆ E such that |E 0 | ≥ |E|/t and such that
every connected component of the graph G0 = (V, E 0 ) has diameter at most 2 · (1 + log |E|)/ logt.
We note that, in particular, if we want |E 0 | ≥ (1 − ε) · |E|, the diameter of the connected components
can be O(ε −1 · log |E|).
2.2 The semidefinite programming relaxation of unique games
In a semidefinite program each variable is a vector, and the objective function and the constraints are
linear in the inner products of the vectors.
To give a semidefinite programming relaxation of unique games, it is convenient to first give an
integer programming formulation of the program, in which variables are constrained to be integers, and
then relax the formulation to a semidefinite programming relaxation.
We consider the following integer programming formulation of unique games. We assume without
loss of generality that the set S equals {1, . . . , |S|}. For every variable u of the unique game, we have
k := |S| boolean variables u1 , . . . , uk in the integer program, with the intended meaning that if u = i then
ui = 1 and u j = 0 for j 6= i. The objective function contains one term ∑i∈S v f (i) ui for each constraint
v = f (u). Hence, our integer programing formulation is as follows:
max ∑e=(u,v)∈E ∑i∈S v fe (i) ui
Subject to
ui · u j = 0 (∀u ∈ V, ∀i, j ∈ [k], i 6= j)
∑i∈S ui = 1 (∀u ∈ V )
ui ∈ {0, 1} (∀u ∈ V )
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 118
A PPROXIMATION A LGORITHMS FOR U NIQUE G AMES
We can obtain a first semidefinite programming relaxation by replacing each integral variable ui with
a vector variable ui , and integer multiplication with inner products.
max ∑e=(u,v)∈E ∑i∈S v fe (i) ui
Subject to
(2.1)
ui · u j = 0 (∀u ∈ V, ∀i, j ∈ [k], i 6= j)
∑i∈S kui k2 = 1 (∀u ∈ V )
We find it convenient to formulate the objective function in a different, but equivalent, way. Let
{v}v∈V be a feasible solution to (2.1) and let v = fe (u) be a constraint of the unique game. Then the
contribution of the constraint to the objective function satisfies
∑ kv f (i) − ui k2 = ∑ kv f (i) k2 + kui k2 − 2v f (i) · ui = 2 − 2 ∑ v f (i) .
e e e u,v
i∈S i∈S i∈S
This means that we can equivalently rewrite the objective function of (2.1) as
!
1
∑ 1 − ∑ kv fe (i) − ui k2 .
e=(u,v)∈E i∈S 2
The semidefinite programming solution that we shall use has the above formulation of the objective
function and, in addition, the “triangle inequalities”:
max ∑e=(u,v)∈E 1 − ∑i∈S 21 kv fe (i) − ui k2
Subject to
ui · u j = 0 (∀u ∈ V, ∀i, j ∈ [k], i 6= j)
(2.2)
∑i∈S kui k2 = 1 (∀u ∈ V )
kwh − ui k2 ≤ kwh − v j k2 + kv j − ui k2 (∀u, v, w ∈ V, ∀i, j, h ∈ [k])
kv j − ui k2 ≥ kv j k2 − kui k2 (∀u, v ∈ V, ∀i, j ∈ [k])
The “triangle inequalities” are valid for integral 0/1 solutions, because if a, b ∈ {0, 1} then |a − b|2 =
|a − b|, and so they reduce to the standard triangle inequalities for the absolute value.
Feige and Lovász [8] and Khot [11] use a slightly different formulation, and it is not clear (to us)
whether the SDP (2.2) is equivalent or not to the ones in [8, 11].
3 The SDP-based algorithm for general unique games
We shall first present a rounding scheme that works well in instances where the constraint graph has
small diameter and where every edge gives a large contribution to the objective function; then we will
use the Leighton-Rao decomposition theorem to reduce general instances to instances of logarithmic
diameter.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 119
L UCA T REVISAN
3.1 The rounding procedure: Analysis on “nice” instances
In this section we shall analyze the following randomized rounding procedure for solutions to the SDP
(2.2).
Algorithm ROUND
Input: a vector solution {vi }v∈V,i∈[k] to the SDP (2.2)
Output: an assignment A : V → [k] to the variables of the unique game
• Fix arbitrarily a vertex r
• Pick at random a value i ∈ [k] with probability kri k2 , and set A(r) := i;
• For every other variable v, find the j that minimizes the “distance” kv j − ri k2 , and assign
A(v) := j.
We shall prove that algorithm ROUND satisfies a large fraction of the constraints, on average, pro-
vided that the constraint graph has small diameter and that we start from a vector solution in which every
edge has a large contribution to the objective function.
Lemma 3.1. Let (G, [k], { fe }) be a unique game such that G has diameter d, and let {vi }v∈V,i∈[k] be a
vector solution to the SDP (2.2) such that every edge contributes at least 1 − δ to the objective func-
tion. Then, for every constraint v = fv,u (u) in the unique game, the probability that the assignment of
algorithm ROUND satisfies the constraint is at least 1 − δ · (8d + 4).
Before going into the proof of Lemma 3.1, it is helpful to first consider the simplified case in which
all the constraints in the unique game are equality constraints. (Indeed, this case contains all the difficul-
ties of the general case.) The assumption that each constraint contributes at least 1 − δ to the objective
function means that for every vertices u, v for which we have the constraint u = v we also have
∑ kui − vi k2 ≤ 2δ .
i∈[k]
In general, we may think of our vector solution as defining a “distance” ∑i∈[k] kui − vi k2 between any
two pairs of vertices u, v, and, because of the triangle inequalities in SDP (2.2), this “distance” satisfies
the triangle inequality as well. Since any two vertices are within distance at most d from each other
(and, in particular, from r) in the constraint graph, we have
∑ kri − vi k2 ≤ 2dδ
i∈[k]
for every vertex v. A geometric interpretation of algorithm ROUND (Lemma 3.2 below) allows us
to conclude that A(r) = A(v) with probability at least 1 − 4dδ . This implies that for every constraint
u = v there is a probability at least 1 − 8dδ that we have both A(r) = A(u) and A(r) = A(v), and so the
constraint is satisfied with probability at least 1 − 8dδ .
Turning to the proof of Lemma 3.1, we begin with the following result about the distribution of
outputs of algorithm ROUND.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 120
A PPROXIMATION A LGORITHMS FOR U NIQUE G AMES
Lemma 3.2. Let (G, [k], { fe }) be a unique game, {vi }v∈V,i∈[k] be a vector solution to the SDP (2.2), v be
a vertex and f be a permutation such that
∑ kri − v f (i) k2 ≤ δ .
i∈[k]
Then, with probability at least 1 − 2δ over the random choices of algorithm ROUND we have A(v) =
f (A(r)).
Proof. Let B be the set of values i such that f (i) is not the values j that minimizes kri − v j k2 . Then we
have
P[A(v) 6= f (A(r))] = ∑ kri k2 .
i∈B
Now we claim that, for every i ∈ B, we have
kri k2 ≤ 2 · kri − v f (i) k2 .
This follows from the following geometric claim, by setting c ← ri , b ← v j , a ← v f (i) , where j is the
minimizer of kri − v j k2 .
Claim 3.3. Let a, b, c be three vectors such that {0, a, b, c} is a metric space with respect to the
Euclidean-squared distance, a, b are orthogonal, and kc − ak2 ≥ kc − bk2 . Then
kck2 ≤ 2 · kc − ak2 .
Proof. We consider three cases: if c is a long vector relative to a, then the claim is immediate; if c is
short relative to a, but long relative to b, then it must be far from b and, for a stronger reason, from a.
Finally, if c is about the same length as b and a, then, considering that b and a form a 90 degree angle,
and that c is closer to b than to a, it must be quite far from a.
Formally, the three cases are:
1. If kak2 ≤ 12 kck2 , then kc − ak2 ≥ kck2 − kak2 ≥ 21 kck2 .
2. If kbk2 ≤ 12 kck2 , then kc − ak2 ≥ kc − bk2 ≥ kck2 − kbk2 ≥ 12 kck2 .
3. If kak2 , kbk2 ≥ 21 kck2 , then from the triangle inequality
kb − ak2 ≤ kb − ck2 + kc − ak2 ≤ 2kc − ak2
and by the Pythagorean theorem and the orthogonality of a and b we have
kb − ak2 = kbk2 + kak2
so that
1 1 1 1
kc − ak2 ≥ kb − ak2 = kak2 + kbk2 ≥ kck2 .
2 2 2 2
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 121
L UCA T REVISAN
Hence,
P[A(v) 6= f (A(r))] = ∑ kri k2 ≤ 2 ∑ kri − v f (i) k2 ≤ 2 ∑ kri − v f (i) k2 ≤ 2δ .
i∈B i∈B i∈[k]
We can now analyze how algorithm ROUND performs on any given constraint and prove Lemma 3.1.
Proof of Lemma 3.1. Let (u, v) be a constraint in G, and consider the path r = u0 , u1 , . . . , ut = u, ut+1 = v
where r, u1 , . . . , ut−1 , u is a path from r to u of length t ≤ d in G.
For ` = 0, . . . ,t + 1, let fi be the composition of the permutations corresponding to the path from r
to u` , that is
f0 (x) := x
f` (x) := f(u` ,u`−1 ) ( f`−1 (x)) .
We claim that there is a probability at least 1 − δ · 4t that A(u) = ft (A(r)).
By writing the difference ri − u ft (i) as a telescopic sum, and then using the triangle inequality in the
SDP formulation, we have
t−1
∑ kri − u ft (i) k2 = ∑ k ∑ u`f` (i) − u`+1
f`+1 (i) k
2
i∈[k] i∈[k] `=0
t−1
≤ ∑ ∑ ku`f (i) − u`+1
` f (i) k
2
`+1
i∈[k] `=0
t−1
= ∑ ∑ ku`j − u`+1
f u` ,u`+1
( j) k
2
`=0 j∈[k]
≤ t · 2δ .
Now we can invoke Lemma 3.2 and see that the probability that A(u) = ft (A(r)) is at least 1 − δ · 4t.
The same argument shows that with probability at least 1 − δ · 4 · (t + 1) we A(v) = ft+1 (A(r)). By
a union bound, it follows that there is a probability at least 1 − δ · (8t + 4) that both events happen, in
which case A(v) = f(v,u) (A(u)).
3.2 The general case: Proof of Theorem 1.1
In this section we prove the following result.
Theorem 3.4. There is a constant c and a polynomial time algorithm, that, given an instance of unique
games and a solution to the SDP (2.2) of cost at least
cε 3
1− · |E| ,
log n
finds a solution for the unique game that satisfies at least a 1 − ε fraction of the constraints.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 122
A PPROXIMATION A LGORITHMS FOR U NIQUE G AMES
Suppose that the SDP relaxation of a unique game (G = (V, E), S, { fe }e∈E ) has a solution of cost
at least (1 − γ) · |E|, where γ = cε 3 / log n (we will fix c later). Then for all but an ε/3 fraction of the
constraints, their contribution to the objective function is at least 1 − 3γ/ε = 1 − 3cε 2 / log n.
The algorithm of Theorem 3.4 is as follows:
1. Remove the constraints whose contribution is smaller than 1 − 3γ/ε.
2. Apply the Leighton-Rao decomposition of Lemma 2.1 with t = 1/(1 − ε/3) to the residual graph.
3. Use the algorithm of Lemma 3.1 to satisfy at least 1 − ε/3 fraction of the constraints in each
connected component of the residual graph that we obtain after steps (1) and (2).
The first step removes at most |E|ε/3 edges and, in the residual graph, every edge contributes at
least 1 − 3cε 2 / log n to the objective function.
The second step removes at most |E|ε/3 edges, and the residual graph breaks up into connected
components of diameter at most d = O((log n)/ε).
The third step can be executed as required, provided that the constant c satisfies
3cε 2 ε
1− ≥ 1− ,
(log n) 24(d + 1)
that is, c < (log n)/(72 · (d + 1) · ε). Since we had d = O((log n)/ε), c is indeed an absolute constant.
Overall, we have found a solution that contradicts at most ε · |E| constraints, and so we have a proof
of Theorem 3.4 and of the first part of Theorem 1.1.
To prove the “furthermore” part of Theorem 1.1, we use the same algorithm but set the parameters
as follows: in the first step, remove the edges that contribute less than 1 − δ /2 to the objective function,
and in the second step, find in the residual graph a decomposition of diameter, say, 1/(100δ ) in which
at least a 1/nO(δ ) fraction of the edges are not removed.
4 Linear unique games
We call a group of permutations linear if every permutation other than the identity has at most one fixed
point, and we call an instance of unique games a linear unique game if the permutations occurring in the
instance generate a linear group.
Linear unique games arise in contexts in which every constraint is an algebraic equation. One ex-
ample of linear unique games are those where S = F, for a finite field F, and every constraint is a linear
equation x = ay + b, a 6= 0. Another example is given by games where S = F and every constraint is an
equation of the form x − y = a.
As before, we first prove a result that applies only to instances with a small-diameter constraint
graph, and then use the Leighton-Rao decomposition to extend the algorithm to arbitrary instances.
4.1 The low-diameter case
If we are given a linear unique game in a small-diameter graph, we are able either to satisfy all constraints
or to find a small unsatisfiable sub-instance.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 123
L UCA T REVISAN
Lemma 4.1. There is a polynomial time algorithm that given a linear unique game (G =
(V, E), { fe }e∈E , S) such that the graph G has diameter at most d, and given a rooted spanning tree T of
G of depth at most d, either finds an assignment that satisfies all constraints or finds an unsatisfiable
sub-instance of size at most 4d + 2.
Proof. For every vertex v, denote by `v the composition of the permutations fe along the path from r to
v in T ; let `r be the identity permutation.
Our algorithm considers, for each i ∈ S, the assignment Ai (v) := `v (i). Each such assignment clearly
satisfies all the constraints in the spanning tree.
Consider a constraint v = fv,u (u) not in the spanning tree. Then the constraint is satisfied by Ai
provided that lv (i) = fv,u `u (i), that is, i = lv−1 ( fv,u (`u (i))). This means that Ai satisfies the constraint if
and only if i is a fixed point of the linear permutation lv−1 ( fv,u (`u (·))). There are three possibilities:
1. The permutation lv−1 ( fv,u (`u (·))) is the identity; then the constraint will be satisfied by every Ai .
2. The permutation lv−1 ( fv,u (`u (·))) has exactly one fixed point iu,v ; we call it the critical value for
the constraint (u, v).
3. The permutation lv−1 ( fv,u (`u (·))) has no fixed point. then we say that (u, v) is inconsistent.
If the unique game contains an inconsistent constraint (u, v), then the path from r to u in T , the path
from r to v in T , and the constraint (u, v) form an unsatisfiable subinstance of size 2d + 1.
If the unique game contains two constraints (u, v) and (w, z) having two distinct critical values, then
the paths from r to u, v, w and z in T , plus the two constraints (u, v) and (w, z) are an unsatisfiable
sub-instance of size 4d + 2.
In all other cases, there is an i such that Ai satisfies all the constraints.
4.2 The general case
We can now prove Theorem 1.2.
Proof of Theorem 1.2. Given a linear unique game (G = (V, E), { fe }, S) and a parameter ε we apply
the Leighton-Rao decomposition and delete at most ε|E|/2 edges so that in the residual graph every
connected component has diameter at most d = O(ε −1 log |E|). We apply Lemma 4.1 in each connected
component, and we either find an assignment that satisfies all the constraints in E 0 or we find a small
“counterexample” of size at most 4d + 2.
In the former case we simply halt and output the assignment. In the latter case we remove the
constraints in the unsatisfiable subinstance from G, and then recompute the low-diameter decomposition,
and so on. Formally, the algorithm is as follows
1. Apply the Leighton-Rao algorithm of Lemma 2.1 to G, and remove at most ε|E|/2 edges from G
so that in the residual graph G0 every connected component has diameter d.
2. Apply the algorithm of Lemma 4.1 to each connected component of G0 .
3. If the previous step finds satisfying assignments that, together, satisfy all the constraints of G0 ,
output the assignments and halt.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 124
A PPROXIMATION A LGORITHMS FOR U NIQUE G AMES
4. Otherwise, remove from G the “counterexamples” of size ≤ 4d + 2 found in step (2) and go to
step (1).
Suppose that there is an assignment that satisfies at least a 1 − ε/(8d + 4) fraction of the constraints.
Then, if we let U be the number of unsatisfiable sub-instances found by the algorithm, we must have
U ≤ ε|E|/(8d + 4), and so the number of edges removed through all phases is at most ε|E|/2. In the
last phase, the algorithm removes at most ε|E|/2 other edges for the low-diameter decomposition, and
then satisfies all (1 − ε)|E| remaining constraints.
To prove the “furthermore” part of Theorem 1.2, we use decompositions p into components of diame-
ter 2 · (log 2|E|)/ log log |E|, which can be found by deleting at most a 1/ log |E| fraction of the edges,
and then use the same analysis.
5 d-to-d games
This section follows once more the pattern of providing a good approximation in instances with a low-
diameter constraint graph, and then giving a reduction from the general case to the special case, using
the Leighton-Rao decomposition theorem.
5.1 Approximation algorithm for low-diameter instances
Lemma 5.1. There is a polynomial time algorithm that, on input a satisfiable d-to-d game (G =
(V, E), {Pe }, S) such that G has diameter t, finds an assignment that satisfies at least a 1/d 2k fraction of
the constraints.
Proof. Let r be a vertex of G such that every other vertex is at distance ≤ t from r, and let T be a
spanning tree of G of depth t rooted at r. Let A be a satisfying assignment. “Guess” the value A(r), then,
for i = 1, . . . ,t, consider all vertices u at distance i from r and compute a list Lu of ≤ d i values of S such
that A(u) is guaranteed to be an element of Lu . To do so, note that if we have computed a list Lu of size `
for a vertex u, and if (u, v) is an edge, then we can compute the list for v of size at most d` by including,
for every a ∈ Lu , the at most d values b such that Pu,v (a, b) = 1.
Once the lists have been computed, for every vertex u we randomly pick an assignment from Lu .
Every vertex has probability at least 1/d t of being assigned the correct value, and so every constraint
has probability at least 1/d 2t of being satisfied.
5.2 Proof of Theorem 1.3
√
We now prove Theorem 1.3. Fix t =p 2 log n·log d . Find a partition of the set of vertices of G such that
each component has diameter k = O( log n/ log d) and a 1/t fraction of the total√weight of the edges
are within the components. Lemma 5.1 gives us a way to satisfy
√ a 1/d 2k = 1/2O( log n·log d) fraction of
the edges within the component. Overall, we satisfy a 1/2 O( log n·log d) fraction of the constraints.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 125
L UCA T REVISAN
Acknowledgements
I wish to acknowledge Elchanan Mossel’s contribution to this research, and his several very useful
suggestions. I wish to thank Robi Krauthgamer and James Lee for suggesting the use of semidefinite
programming, proposing the SDP formulation (2.2) and helping with the proof of Claim 3.3.
I thank Kenji Obata for sharing his understanding of graph decomposition procedures while he was
working on [19]. Avi Eyal, Piotr Indyk, Salil Vadhan, and the anonymous referees, among others, gave
very helpful feedback about the presentation of our algorithms.
References
[1] * S ANJEEV A RORA , S UBHASH K HOT, A LEXANDRA KOLLA , DAVID S TEURER , M ADHUR T UL -
SIANI , AND N ISHEETH V ISHNOI : Unique games on expanding constraint graphs are easy. In Proc.
40th STOC, pp. 21–28. ACM Press, 2008. [STOC:10.1145/1374376.1374380]. 1.4
[2] * P ER AUSTRIN: Balanced max 2-SAT might not be the hardest. In Proc. 39th STOC, pp. 189–197.
ACM Press, 2007. [STOC:10.1145/1250790.1250818]. 1
[3] * P ER AUSTRIN: Towards sharp inapproximability for any 2-CSP. In Proc. 48th FOCS, pp. 307–
317. IEEE Computer Society, 2007. [FOCS:10.1109/FOCS.2007.73]. 1
[4] * M OSES C HARIKAR , KONSTANTIN M AKARYCHEV, AND Y URY M AKARYCHEV: Near-
optimal algorithms for unique games. In Proc. 38th STOC, pp. 205–214. ACM Press, 2006.
[STOC:1132516.1132547]. 1.4
[5] * S HUCHI C HAWLA , ROBERT K RAUTHGAMER , R AVI K UMAR , Y UVAL R ABANI , AND
D.S IVAKUMAR: On the hardness of approximating multicut and sparsest-cut. In Proc.
20th IEEE Conf. on Computational Complexity, pp. 144–153. IEEE Computer Society, 2005.
[CCC:10.1109/CCC.2005.20]. 1
[6] * E DEN C HLAMTAC , KONSTANTIN M AKARYCHEV, AND Y URY M AKARYCHEV: How to play
unique games using embeddings. In Proc. 47th FOCS, pp. 687–696. IEEE Computer Society,
2006. [FOCS:10.1109/FOCS.2006.36]. 1.4
[7] * I RIT D INUR , E LCHANAN M OSSEL , AND O DED R EGEV: Conditional hardness for approximate
coloring. In Proc. 38th STOC, pp. 344–353. ACM Press, 2006. [STOC:1132516.1132567]. 1
[8] * U RI F EIGE AND L ÁSZL Ó L OV ÁSZ: Two-prover one round proof systems: Their power and their
problems. In Proc. 24th STOC, pp. 733–741. ACM Press, 1992. [STOC:129712.129783]. 1, 2.2
[9] * U RIEL F EIGE AND DANIEL R EICHMAN: On systems of linear equations with two variables per
equation. In 7th International Workshop on Approximation Algorithms for Combinatorial Opti-
mization Problems (APPROX’04), pp. 117–127. Springer, 2004. [Springer:uk7fpuul45c5h6j5]. 1,
1.1
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 126
A PPROXIMATION A LGORITHMS FOR U NIQUE G AMES
[10] * A NUPAM G UPTA AND K UNAL TALWAR: Approximating unique games. In Proc.
17th ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 99–106. ACM Press, 2006.
[SODA:1109557.1109569]. 1.4
[11] * S UBHASH K HOT: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp.
767–775. ACM Press, 2002. [STOC:509907.510017]. 1, 2, 2.2
[12] * S UBHASH K HOT, G UY K INDLER , E LCHANAN M OSSEL , AND RYAN O’D ONNELL: Optimal
inapproximability results for MAX-CUT and other two-variable CSPs? In Proc. 45th FOCS, pp.
146–154. IEEE Computer Society, 2004. [FOCS:10.1109/FOCS.2004.49]. 1
[13] * S UBHASH K HOT AND RYAN O’D ONNELL: SDP gaps and UGC-hardness for MAX-
CUTGAIN. In Proc. 47th FOCS, pp. 217–226. IEEE Computer Society, 2006.
[FOCS:10.1109/FOCS.2006.67]. 1
[14] * S UBHASH K HOT AND O DED R EGEV: Vertex cover might be hard to approximate to within
2 − ε. J. Comput. System Sci., 74:335–349, 2008. Preliminary version in Proc. CCC’03.
[JCSS:10.1016/j.jcss.2007.06.019]. 1
[15] * S UBHASH K HOT AND N ISHEETH V ISHNOI: The unique games conjecture, integrality gap for
cut problems and the embeddability of negative type metrics into `1 . In Proc. 46th FOCS, pp.
53–63. IEEE Computer Society, 2005. [FOCS:10.1109/SFCS.2005.74]. 1
[16] * F RANK T. L EIGHTON AND S ATISH R AO: Multicommodity max-flow min-cut theo-
rems and their use in designing approximation algorithms. J. ACM, 46:787–832, 1999.
[JACM:331524.331526]. 1.2, 2.1, 2.1
[17] * R AJESKAR M ANOKARAN , S EFFI NAOR , P RASAD R AGHAVENDRA , AND ROY S CHWARTZ:
SDP gaps and UGC hardness for multiway cut, 0-extension and metric labeling. In Proc. 40th
STOC, pp. 11–20. ACM Press, 2008. [STOC:10.1145/1374376.1374379]. 1
[18] * E LCHANAN M OSSEL , RYAN O’D ONNELL , AND K RZYSZTOF O LESZKIEWICZ: Noise stability
of functions with low influences: invariance and optimality. In Proc. 46th FOCS, pp. 21–30. IEEE
Computer Society, 2005. [FOCS:10.1109/SFCS.2005.53]. 1
[19] * K ENJI O BATA: Approximate max-integral-flow/min-multicut theorems. In Proc. 36th STOC, pp.
539–545. ACM Press, 2004. [STOC:1007352.1007433]. 5.2
[20] * RYAN O’D ONNELL AND Y I W U: An optimal SDP algorithm for Max-Cut, and
equally optimal long code tests. In Proc. 40th STOC, pp. 335–344. ACM Press, 2008.
[STOC:10.1145/1374376.1374425]. 1
[21] * P RASAD R AGHAVENDRA: Optimal algorithms and inapproximability results for every CSP? In
Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [STOC:10.1145/1374376.1374414]. 1
[22] * R AN R AZ: A parallel repetition theorem. SIAM J. Computing, 27(3):763–803, 1998. Preliminary
version in STOC’95. [SICOMP:10.1137/S0097539795280895, STOC:225058.225181]. 1.1
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 127
L UCA T REVISAN
[23] * A LEX S AMORODNITSKY AND L UCA T REVISAN: Gowers uniformity, influence of variables,
and PCPs. In Proc. 38th STOC, pp. 11–20. ACM Press, 2006. [STOC:10.1145/1132516.1132519].
1
AUTHOR
Luca Trevisan
Associate Professor
Department of Electrical Engineering and Computer Science
University of California
Berkeley, CA 94720-1776
luca EECS Berkeley edu
http://www.cs.berkeley.edu/∼luca
ABOUT THE AUTHOR
L UCA T REVISAN is an associate professor of computer science at U. C. Berkeley. Luca
received his Laurea (B. Sc.) degree in 1993 and his Dottorato (Ph. D.) in 1997, both from
the University of Rome La Sapienza, advised by Pierluigi Crescenzi. Before coming
to Berkeley in 2000, Luca was a post-doc at MIT and at DIMACS, and an assistant
professor at Columbia University.
Luca’s research is in theoretical computer science, and most of his work has been about
the approximability of combinatorial optimization problems and about the power of
randomness in computation.
Luca received the STOC’97 student paper award and the 2000 Oberwolfach Prize. He
was an invited speaker at ICM 2006 in Madrid.
Luca lives, beyond his means, in expensive San Francisco, where he enjoys the film
festivals, the neighborhood coffee shops, and the food. When not in San Francisco or
Berkeley, Luca can often be found in Rome, New York, or Beijing.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 111–128 128