Authors Venkatesan Guruswami, Ali Kemal Sinop,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435
www.theoryofcomputing.org
Improved Inapproximability Results for
Maximum k-Colorable Subgraph∗
Venkatesan Guruswami† Ali Kemal Sinop‡
Received January 28, 2010; Revised February 24, 2013; Published May 24, 2013
Abstract: We study the maximization version of the fundamental graph coloring problem.
Here the goal is to color the vertices of a k-colorable graph with k colors so that a maximum
fraction of edges are properly colored (i. e., their endpoints receive different colors). A
random k-coloring properly colors an expected fraction 1 − 1/k of edges. We prove that
given a graph promised to be k-colorable, it is NP-hard to find a k-coloring that properly
colors more than a fraction ≈ 1 − 1/(33k) of edges. Previously, only a hardness factor of
1 − O 1/k2 was known. Our result pins down the correct asymptotic dependence of the
approximation factor on k. Along the way, we prove that approximating the Maximum
3-Colorable Subgraph problem within a factor greater than 32/33 is NP-hard.
Using semidefinite programming, it is known that one can do better than a random
coloring and properly color a fraction 1 − 1/k + 2 ln(k)/k2 of edges in polynomial time. We
show that, assuming the 2-to-1 conjecture, it is hard to properly color (using k colors) more
than a fraction 1 − 1/k + O(ln(k)/k2 ) of edges of a k-colorable graph.
ACM Classification: F.2.2, G.1.6, G.2.2
AMS Classification: 68W17, 68R10
Key words and phrases: hardness of approximation, graph coloring, constraint satisfaction, probabilisti-
cally checkable proof
∗ An extended abstract of this paper appeared in the Proceedings of the 12th International Workshop on Approximation,
Randomization, and Combinatorial Optimization, 2009 [7].
† Research supported in part by a Packard Fellowship.
‡ Research supported in part by a Packard Fellowship.
© 2013 Venkatesan Guruswami and Ali Kemal Sinop
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2013.v009a011
V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP
1 Introduction
1.1 Problem statement
A graph G = (V, E) is said to be k-colorable for some positive integer k if there exists a k-coloring
χ : V → {1, 2, . . . , k} such that for all edges (u, v) ∈ E, χ(u) 6= χ(v). For k ⩾ 3, finding a k-coloring of a
k-colorable graph is a classic NP-hard problem. The problem of coloring a graph with the fewest number
of colors has been extensively studied. In this paper, our focus is on hardness results for the following
maximization version of graph coloring: Given a k-colorable graph (for some fixed constant k ⩾ 3), find
a k-coloring that maximizes the fraction of properly colored edges. Throughout this paper, for a given
coloring, we say an edge is miscolored by this coloring if both of its endpoints receive the same color
and properly colored otherwise. If no such edge exists, we call the coloring proper. Note that for k = 2
the problem is trivial—one can find a proper 2-coloring in polynomial time when the graph is bipartite
(2-colorable).
We will call this problem Max k-Colorable Subgraph. The problem is equivalent to partitioning the
vertices into k parts so that a maximum number of edges are cut. This problem is more popularly referred
to as Max k-Cut in the literature; however, in the Max k-Cut problem the input is an arbitrary graph that
need not be k-colorable. To highlight this difference, we use Max k-Colorable Subgraph to refer to this
variant. We stress that we will use this convention throughout the paper: Max k-Colorable Subgraph
always refers to the “perfect completeness” case, when the input graph is k-colorable.1 Since our focus
is on hardness results, we note that this restriction only makes our results stronger.
A factor α = αk approximation algorithm for Max k-Colorable Subgraph is an efficient algorithm
that given as input a k-colorable graph outputs a k-coloring that properly colors at least a fraction α of
the edges. We say that Max k-Colorable Subgraph is NP-hard to approximate within a factor β if no
factor β approximation algorithm exists for the problem unless P = NP. The goal is to determine the
approximation threshold of Max k-Colorable Subgraph: the largest α as a function of k for which a factor
α approximation algorithm for Max k-Colorable Subgraph exists.
1.2 Previous results
The algorithm which simply picks a random k-coloring, without even looking at the graph, properly colors
an expected fraction 1 − 1/k of edges. Frieze and Jerrum [4] used semidefinite programming to give a
polynomial time factor 1 − 1/k + 2 ln k/k2 approximation algorithm for Max k-Cut, which in particular
means the algorithm will color at least this fraction of edges in a k-colorable graph. This remains the
best approximation guarantee for Max k-Colorable Subgraph known to date. Khot, Kindler, Mossel, and
O’Donnell [11] showed that obtaining an approximation factor of 1 − 1/k + 2 ln k/k2 + Ω(ln ln k/k2 ) for
Max k-Cut is Unique Games-hard, thus showing that the Frieze-Jerrum algorithm is essentially the best
possible. However, due to the “imperfect completeness” inherent to the Unique Games conjecture, this
hardness result does not hold for Max k-Colorable Subgraph when the input is required to be k-colorable.
For Max k-Colorable Subgraph, the best hardness known prior to our work was a factor 1 − Θ(1/k2 ).
This is obtained by combining an inapproximability result for Max 3-Colorable Subgraph due to Pe-
trank [15] with a reduction from Papadimitriou and Yannakakis [14]. It is a natural question whether is
1 While a little non-standard, this makes our terminology more crisp, as we can avoid repeating the fact that the hardness
holds for k-colorable graphs in our statements.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 414
I MPROVED I NAPPROXIMABILITY R ESULTS FOR M AXIMUM k-C OLORABLE S UBGRAPH
an efficient algorithm that could properly color a fraction 1 − 1/k1+ε of edges given a k-colorable graph
for some absolute constant ε > 0. The existing hardness results do not rule out the possibility of such an
algorithm.
For Max k-Cut, an NP-hardness factor was shown by Kann, Khanna, Lagergren, and Panconesi [9]—
for some absolute constants β > α > 0: They showed that it is NP-hard to distinguish graphs that have
a k-cut in which a fraction (1 − α/k) of the edges cross the cut from graphs whose Max k-Cut value
is at most a fraction (1 − β /k) of edges. This hardness result was proven by reduction from MaxCut.
Since MaxCut is easy when the graph is 2-colorable, this reduction does not yield any hardness for Max
k-Colorable Subgraph.
1.3 Our results
Petrank [15] showed the existence of a γ0 > 0 such that it is NP-hard to find a 3-coloring that properly
colors more than a fraction (1 − γ0 ) of the edges of a 3-colorable graph. The value of γ0 in [15] was left
unspecified and would be very small if calculated. The reduction in [15] was rather complicated, involving
expander graphs and starting from the weaker hardness bounds for bounded occurrence satisfiability
(as opposed to, say, problems for which deciding between perfect completeness and 1/2 soundness is
hard). We prove that the NP-hardness holds with γ0 = 1/33. In other words, it is NP-hard to obtain
an approximation ratio bigger than 32/33 for Max 3-Colorable Subgraph. The reduction is from the
constraint satisfaction problem corresponding to the adaptive 3-query PCP with perfect completeness
from [6]. Note that we are interested in making the constant γ0 as large as possible, which is the reason
why we went through a different reduction than simply re-using Petrank’s hardness result [15].
By a reduction from Max 3-Colorable Subgraph, we prove that for every k ⩾ 3, the Max k-Colorable
Subgraph is NP-hard to approximate within a factor greater than ≈ 1 − 1/(33k) (Theorem 2.9). This
identifies the correct asymptotic dependence on k of the best possible approximation factor for Max
k-Colorable Subgraph. The reduction is similar to the one in [9], though some crucial changes have to be
made in the construction and some new difficulties overcome in the soundness analysis when reducing
from Max 3-Colorable Subgraph instead of MaxCut. Furthermore the constant in front of 1/k is the same
with constant γ0 of 3-coloring case. Any improvement for 3-coloring hardness will immediately apply to
general k-coloring case as well.
In the quest for pinning down the exact approximability of Max k-Colorable Subgraph, we prove the
following conditional result. Assuming the so-called 2-to-1 conjecture (see Definition 3.4, Section 3.1),
it is hard to approximate Max k-Colorable Subgraph within a factor 1 − 1/k + O(ln(k)/k2 ). In other
words, the Frieze-Jerrum algorithm is optimal up to lower order terms in the approximation ratio even for
instances of Max k-Cut where the graph is k-colorable.
Unlike the Unique Games Conjecture (UGC), the 2-to-1 conjecture allows perfect completeness, i. e.,
the hardness holds even for instances where an assignment satisfying all constraints exists. The 2-to-1
conjecture was used by Dinur, Mossel, and Regev [3] to prove that for every constant c ⩾ 4, it is NP-hard
to color a 4-colorable graph with c colors. We analyze a similar reduction for the k-coloring case when
the objective is to maximize the fraction of edges that are properly colored by a k-coloring. Our analysis
uses some of the machinery developed in [3], which in turn extends the invariance principle of [12]. The
hardness factor we obtain depends on the spectral gap of a certain k2 × k2 stochastic matrix.
Remark 1.1. In general it is far from clear which Unique Games-hardness results can be extended to hold
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 415
V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP
with perfect completeness by assuming, say, the 2-to-1 (or some related) conjecture. In this vein, we also
mention the result of O’Donnell and Wu [13] who showed a tight hardness for approximating satisfiable
constraint satisfaction problems on three Boolean variables assuming the d-to-1 conjecture for any fixed
d. While the UGC assumption has led to a nearly complete understanding of the approximability of
constraint satisfaction problems [16], the approximability of satisfiable constraint satisfaction problems
remains a mystery to understand in any generality.
2 Unconditional hardness results for Max k-Colorable Subgraph
We will first prove a hardness result for Max 3-Colorable Subgraph, and then reduce this problem to Max
k-Colorable Subgraph.
2.1 Inapproximability result for Max 3-Colorable Subgraph
Petrank [15] showed that Max 3-Colorable Subgraph is NP-hard to approximate within a factor of (1 − γ0 )
for some constant γ0 > 0. This constant γ0 is presumably very small, since the reduction starts from
bounded occurrence satisfiability and uses expander graphs. We prove a much better inapproximability
factor below, via a simpler proof.
Theorem 2.1 (Max 3-Colorable Subgraph Hardness). The Max 3-Colorable Subgraph problem is NP-
hard to approximate within a factor of 32/33 + ε for every constant ε > 0.
Remark 2.2. In a recent work, Austrin et al. [1] improved the hardness of approximation factor in our
Theorem 2.1 to 16/17 + ε.
For the proof of this theorem, we will reduce from a hard to approximate constraint satisfaction
problem (CSP), stated below. This CSP is related to the adaptive 3-query PCP (with perfect completeness
and soundness 1/2 + ε for any desired constant ε) given in [6], which in turn is based on Håstad’s PCP
for showing tight inapproximability of Max 3SAT on satisfiable instances.
Definition 2.3 (The GLST CSP). An instance of the GLST constraint satisfaction problem will have
variables partitioned into three parts X, Y and Z. Each constraint will be of the form (xi ∨ (Y j = zk )) ∧
(xi ∨ (Y j = zl )), where xi ∈ X, zk , zl ∈ Z are variables (unnegated) and Y j is a literal (Y j ∈ {y j , y j } for some
variable y j ∈ Y). The goal is to find a Boolean assignment to the variables in X ∪ Y ∪ Z that satisfies as
many constraints as possible.
The following hardness result will be our starting point in the reduction establishing Theorem 2.1.
Proposition 2.4. For all constants ε > 0, given an instance of the GLST CSP, it is NP-hard to distinguish
between the following two cases:
• Y ES instances: There is a Boolean assignment to the variables that satisfies all the constraints.
• N O instances: Every Boolean assignment to the variables satisfies at most a fraction (1/2 + ε) of
the constraints.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 416
I MPROVED I NAPPROXIMABILITY R ESULTS FOR M AXIMUM k-C OLORABLE S UBGRAPH
Remark 2.5. Without the restriction that the instance is tripartite (i. e., the x, Y , and z variables come
from disjoint parts) and that the z-variables never appear negated, the above hardness result follows
immediately from [6]. However, these extra structural restrictions can be ensured by an easy modification
to the PCP construction in [6]. The PCP in [6] has a bipartite structure: the proof is partitioned into two
parts called the A-tables and B-tables, and each test consists of probing one bit A( f ) from an A table and 3
bits B(g), B(g1 ), B(g2 ) from the B table, and checking (A( f ) ∨ (B(g) = B(g1 )) ∧ (A( f ) ∨ (B(g) = B(g2 )).
Further these tables are folded, meaning that A( f ) = −A(− f ) and B(g) = −B(−g) are enforced by
construction, and this leads to the occurrence of negations when the PCP checks are viewed as constraints
in the CSP world. In fact, as argued in [5], one does not need the B-table to be folded if one makes a slight
change to the predicate and checks the condition (A( f ) ∨ (B(g) = B(−g1 )) ∧ (A( f ) ∨ (B(g) = B(−g2 )).
Not folding the B-table gives further control to how negations appear in the constraints.
The proof of Proposition 2.4 is based on the observation that the analysis of the PCP construction
in [6] goes through with minor changes, even if (i) the queries at locations g1 and g2 are made in a parallel
C-table instead of also being made in the B table, and (ii) the C-table is not required to be folded (though
the A and B tables are still folded).2 We skip a full formal proof of this as it will take us too far afield into
the inner Fourier-analytic workings of the analysis of [6]. However, in Appendix A, we indicate the main
changes needed in the analysis when a C-table is used. This should suffice to convince those generally
familiar with Håstad’s work [8] about the claim of Proposition 2.4.
Xi Yj Zl
xi yj wj y¯j zl
A′ B′
wj wj
∆(xi )/2 ∆(zl )/2 A B
R
m m
2 2 xi Yj zk zl
m
T 2 F F T
Figure 1: Global gadget for truth value assign- Figure 2: Local gadget for each constraint of the
ments. Blocks Xi , Y j and Zl are replicated for form (xi ∨Y j = zk ) ∧ (xi ∨Y j = zl ). All edges have
all vertices in X, Y and Z. Edge weights are unit weight. Labels A, A0 , B, B0 refer to the local
shown next to each edge. nodes in each gadget.
Proof. Let I be an instance of the GLST CSP with m constraints of the above form on variables
V = X ∪ Y ∪ Z. Let X = {x1 , x2 , . . . , xn1 }, Y = {y1 , y2 , . . . , yn2 } and Z = {z1 , z2 , . . . , zn3 }. From the instance
I we create a graph G for the Max 3-Colorable Subgraph problem as follows. There is a node xi for each
variable xi ∈ X, a node zl for each zl ∈ Z, and a pair of nodes {y j , y j } for the two literals corresponding to
each y j ∈ Y. There are also three global nodes {R, T, F} representing boolean values which are connected
in a triangle with edge weights m/2 (see Fig. 1).
2 Note that these restrictions in the PCP world exactly correspond to the structural restrictions of the CSP instance in
Definition 2.3.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 417
V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP
For each constraint of the CSP, we place the local gadget specific to that constraint shown in Figure 2.
Note that there are 10 edges of unit weight in this gadget. The nodes y j , y j are connected to node R by a
triangle whose edge weights equal w j = (∆(y j ) + ∆(y j ))/2. Here ∆(X) denotes the total number of edges
going from node X into all the local gadgets. Note that ∆(xi ) equals twice the total number of occurrences
of xi in all constraints, and similarly for ∆(y j ) and ∆(y j ). For the z-variables, ∆(zl ) equals the number of
occurrences of zl in constraints of the CSP. The nodes xi and zl connected to R with an edge of weight
∆(xi )/2 and ∆(zl )/2 respectively.
Remark 2.6. It has been shown by Crescenzi, Silvestri and Trevisan [2] that any hardness result for
weighted instances of Max k-Cut carries over to unweighted instances assuming the total edge weight is
polynomially bounded. In fact, their reduction preserves k-colorability, so an inapproximability result for
the weighted Max k-Colorable Subgraph problem also holds for the unweighted version. Therefore all
our hardness results hold for the unweighted Max k-Colorable Subgraph problem.
Let us now prove the completeness and soundness properties of the reduction.
Lemma 2.7 (Completeness). Given an assignment of variables σ : V → {0, 1} which satisfies at least c
of the constraints, we can construct a 3-coloring of G with at most m − c improperly colored edges (each
of weight 1).
Proof. We define the coloring χ : V (G) → [3] in the obvious way, with nodes T , R and F fixed to different
colors. Then define (
χ(T ) if σ (xi ) = 1,
χ(xi ) =
χ(F) else.
and similarly for the nodes y j , zl . Define
(
χ(F) if σ (y j ) = 1,
χ(yi ) =
χ(T ) else.
Now, for the constraints satisfied by this assignment, (xi ∨ (Y j = zk )) ∧ (xi ∨ (Y j = zl )), consider
the corresponding gadget. Let Sugg(A) = [3] \ {χ(xi ), χ(T )} and Sugg(B) = [3] \ {χ(Y j ), χ(zk )} be the
available colors to A and B which can properly color all edges incident to variables. Notice that none of
these sets are empty and since xi ∨ (Y j = zk ) is true, at least one of these sets Sugg(A) and Sugg(B) has
two elements in it. Hence there exists a coloring of A and B from sets Sugg(A) and Sugg(B) such that
χ(A) 6= χ(B). The same argument also holds for A0 and B0 , therefore all edges in this gadget are properly
colored.
For the violated constraints, either Sugg(A) or Sugg(A0 ) has one element. Augmenting that set with
the color χ(xi ) will cause only one edge to be violated.
Lemma 2.8 (Soundness). Given a 3-coloring of G, χ, such that the total weight of edges that are not
properly colored by χ is at most τ < m/2, we can construct an assignment σ 0 : V → {0, 1} to the variables
of the CSP instance that satisfies at least m − τ constraints.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 418
I MPROVED I NAPPROXIMABILITY R ESULTS FOR M AXIMUM k-C OLORABLE S UBGRAPH
Proof. Since τ < m/2, the coloring χ must give three different colors to the nodes T , F, and R. If
χ(xi ) = χ(R), then randomly choosing χ(xi ) from {χ(T ), χ(F)} will, in expectation, make at most half
of the local gadget edges going out of xi improperly colored, which is exactly the value ∆(xi )/2 gained.
So we can assume that χ(xi ) ∈ {χ(T ), χ(F)} for each xi . A similar argument holds for the nodes zl .
Now consider the nodes y j and y j for a variable in Y . If χ(y j ) = χ(R), χ(y j ) = χ(R) or χ(y j ) = χ(y j ),
then randomly choosing (χ(y j ), χ(y j )) from {(χ(T ), χ(F)), (χ(F), χ(T ))} will, in expectation, make at
most half of the local gadget edges going out of nodes y j and y j improperly colored, which is exactly the
value w j gained.
To summarize, we can assume that nodes T ,F and R are colored differently, χ(xi ), χ(Y j ), χ(zl ) ∈
{χ(T ), χ(F)} and χ(y j ) 6= χ(y j ). Thus all edges other than the edges inside the local gadgets are properly
colored by χ, and by assumption at most τ edges are miscolored by χ.
Now define the natural assignment σ 0 that assigns a variable of V the value 1 if the associated variable
received the color χ(T ), and the value 0 if its color is χ(F).
Consider a local gadget, with all edges properly colored, corresponding to the constraint (xi ∨ (Y j =
zk )) ∧ (xi ∨ (Y j = zl )). Assume σ 0 (xi ) = 0, which implies χ(A) = χ(R). Then both neighbors of B besides
A must have the same color, therefore σ (Y j ) = σ (zk ). The other case when σ 0 (xi ) = 1 is similar. Hence
the assignment σ 0 will satisfy this constraint.
Since the local gadgets corresponding to different constraints have disjoint sets of edges, it follows
that the number of constraints violated by the assignment σ 0 is at most τ.
Returning to the proof of Theorem 2.1, the total weight of edges in G is
n3
3m n1 ∆(xi ) n2 ∆(zl ) 27 3 n2 33
10m + +∑ + ∑ 3w j + ∑ = m + ∑ (∆(yi ) + ∆(y j )) = m .
2 i=1 2 j=1 l=1 2 2 2 j=1 2
| {z } | {z } | {z }
m m 2m
By the completeness lemma, Y ES instances of the CSP are mapped to graphs G that are 3-colorable.
By the soundness lemma, N O instances of the CSP are mapped to graphs G such that every 3-coloring
miscolors at least a fraction
(1/2 − ε) 1 − 2ε
=
33/2 33
of the total weight of edges. Since ε > 0 is an arbitrary constant, the proof of Theorem 2.1 is complete.3
2.2 Max k-Colorable Subgraph hardness
Theorem 2.9. For every fixed integer k ⩾ 3 and every ε > 0, it is NP-hard to approximate Max k-Colorable
Subgraph within a factor of
1
1− +ε
33(k + ck ) + ck
where ck = k mod 3 ⩽ 2.
3 Our reduction produced a graph with edge weights, but by Remark 2.6, the same inapproximability factor holds for
unweighted graphs as well.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 419
V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP
Remark 2.10. The hardness factor in Theorem 2.9 can be improved to
1
1− +ε
17(k + ck ) + ck
using the earlier mentioned improved hardness of approximation result for Max 3-Colorable Subgraph
due to Austrin et al. [1].
Proof. We will reduce Max 3-Colorable Subgraph to Max k-Colorable Subgraph and then apply Theo-
rem 2.1. Throughout the proof, we will assume k is divisible by 3. At the end, we will cover the remaining
cases also. The reduction is inspired by the reduction from MaxCut to Max k-Cut given by Kann et
al. [9] (see Remark 2.13). Some modifications to the reduction are needed when we reduce from Max
3-Colorable Subgraph, and the analysis has to handle some new difficulties. The details of the reduction
and its analysis follow.
Let G = (V, E) be an instance of Max 3-Colorable Subgraph. By Theorem 2.1, it is NP-hard to tell if
G is 3-colorable or every 3-coloring miscolors a fraction 1/33 − ε of edges. We will construct a graph H
such that H is k-colorable when G is 3-colorable, and a k-coloring which miscolors at most a fraction
µ of the total weight of edges of H implies a 3-coloring of G with at most a fraction µk of miscolored
edges. Combined with Theorem 2.1, this gives us the claimed hardness of Max k-Colorable Subgraph.
Let Kk/30 denote the complete graph including loops on k/3 vertices. Let G0 be the tensor product graph
between Kk/3 and G, G0 = Kk/3 0 ⊗ G as defined by the following: Identify each node in G0 with (u, i), u ∈
V (G), i ∈ {1, 2, . . . , k/3}. The edges of G0 are ((u, i), (v, i0 )) for (u, v) ∈ E and any i, i0 ∈ {1, . . . , k/3}.
We construct another graph H by making three copies of G0 , and identifying the nodes with
(u, i, j), (u, i) ∈ V (G0 ), j ∈ {1, 2, 3}. The edge set of this new graph is defined in the following way:
There are edges between all nodes of the form (u, i, j) and (u, i0 , j0 ) with weight (2/3)du if either i 6= i0 or
j 6= j0 . Here du is degree of node u.
The total weight of edges in this new graph, H, is equal to
!
3 k 2
k 2
∑ 2 3 du + 2 3 du ⩽ k2 m .
u∈V
Lemma 2.11. If G is 3-colorable, then H is k-colorable.
Proof. Let χG : V (G) → {1, 2, 3} be a 3-coloring of G. Consider the following coloring function for
H, χH : V (H) → {1, 2, . . . , k}. For node (u, i, j), let χH ((u, i, j)) = π j (χG (u)) + 3(i − 1). Here π is the
permutation
1 2 3
, and π j (x) = π(. . . (π( x))) .
2 3 1 | {z }
j times
Equivalently π(x) = x mod 3 + 1.
First let us consider edges of the form {(u, i, j), (v, i0 , j)}. If i 6= i0 , then colors of the endpoints belong
to different windows of size 3 and are therefore different. If i = i0 , we have χ((u, i, j)) − χ((v, i, j)) ≡
χ(u) − χ(v) 6≡ 0 mod 3 since χ is a proper 3-coloring of G.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 420
I MPROVED I NAPPROXIMABILITY R ESULTS FOR M AXIMUM k-C OLORABLE S UBGRAPH
Let us now consider edges of the form {(u, i, j), (u, i0 , j0 )}. Once again, if i 6= i0 , the two endpoints
receive different colors. When i = i0 , j 6= j0 ,
0
χ((u, i, j)) − χ((u, i, j0 )) ≡ π j (u) − π j (u) ≡ j − j0 6≡ 0 mod 3 .
Lemma 2.12. If H has a k-coloring that properly colors a set of edges with at least a fraction (1 − µ) of
the total weight for some µ ∈ [0, 1], then G has a 3-coloring which colors at least a fraction (1 − µk) of
its edges properly.
Proof. Here we only handle the case of k being divisible by 3. We defer the proof for the case of k being
not divisible by 3 to Section 2.3.
Let χH be the coloring of H, Sugguj = {χH ((u, i, j)) | 1 ⩽ i ⩽ k/3} and Suggu = j Sugguj . The total
S
weight of uncut edges in this solution can be written as
2
Ctotal = ∑ 3 duCuwithin +Cbetween , (2.1)
u∈V (G)
where Cuwithin and Cbetween denotes the number of improperly colored (unordered) edges within the copies
of node u and between copies of different vertices u, v ∈ V (G) respectively. We have the following
relations:
3
Cbetween = ∑ ∑ ∑ 1χH ((u,i, j))=χH ((v,i0 , j))
j=1 {u,v}∈E(G) 1⩽i,i0 ⩽k/3
3
⩾∑ ∑ |Sugguj ∩ Suggvj |. (2.2)
j=1 {u,v}∈E(G)
and
−1
|χH (c) ∩ Bu |
Cuwithin = ∑ (Bu = {(u, i, j) | ∀i, j})
c∈Suggu 2
!
1 k
= ∑ |Bu,c |2 − (Bu,c = Bu ∩ χH−1 (c))
2 c∈Sugg 2
u
!2
1 k
⩾ ∑ |Bu,c | − 2
2|Suggu | c∈Sugg
(Cauchy-Schwarz)
u
k k k |Suggu | |Suggu |
= −1 = ⩾ .
2 |Suggu | 2 |Suggu | 2
Now we will find a (random) 3-coloring χG for G. Pick c from {1, 2, . . . , k} uniformly at random. If
c∈
/ Suggu , select χG (u) uniformly at random from {1, 2, 3}. If c ∈ Suggu , set χG (u) = j if j is the smallest
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 421
V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP
index for which c ∈ Sugg j (u). With this coloring χG (u), the probability that an edge {u, v} ∈ E(G) will
be improperly colored is:
!
3 j j
1
Pr [χG (u) = χG (v)] ⩽ ∑ Prc c ∈ Suggu ∩ Suggv + 3 Prc c ∈ Suggu , c ∈ Suggv
j=1
1 1
+ Prc c ∈ Suggu , c ∈ Suggv + Prc c ∈ Suggu , c ∈ Suggv
3 ! 3
3 j j
|Suggu ∩ Suggv | |Suggu | |Suggv |
⩽ ∑ + + .
j=1 k 3k 3k
We can thus bound the expected number of miscolored edges in the coloring χG as follows.
" # " #
3
|Sugguj ∩ Suggvj |
|Suggu | |Suggv |
E ∑ 1χG (u)=χG (v) ⩽ ∑ ∑ + +
{u,v}∈E(G) {u,v}∈E j=1 k 3k 3k
1 between du
⩽ C + ∑ |Suggu | (using (2.2))
k u∈V (G)
3
1 between 2du within Ctotal
⩽ C + ∑ C = .
k u∈V (G)
3 u k
This implies that there exists a 3-coloring of G for which the number of improperly colored edges in G is
at most Ctotal /k. Therefore if H has a k-coloring which improperly colors at most a total weight µk2 m of
edges, then there is a 3-coloring of G which colors improperly at most a fraction µk2 m/(km) = µk of its
edges.
This completes the proof of Theorem 2.9 when k is divisible by 3. The other cases are easily handled
by adding k mod 3 extra nodes connected to all vertices by edges of suitable weight, which we describe
in the following section.
Remark 2.13 (Comparison to [9]). The reduction of Kann et al. [9] converts an instance G of MaxCut to
the instance G0 = Kk/2
0 ⊗ G of Max k-Cut. Edge weights are picked so that the optimal k-cut of G0 will
give a set Su of k/2 different colors to all vertices in each k/2 clique (u, i), 1 ⩽ i ⩽ k/2. This enables
converting a k-cut of G0 into a cut of G based on whether a random color falls in Su or not. In the
3-coloring case, we make 3 copies of G0 in an attempt to enforce three “translates” of Su , and use those to
define a 3-coloring from a k-coloring. But we cannot ensure that each k-clique is properly colored, so
these translates might overlap and a more careful soundness analysis is needed.
2.3 Handling k not divisible by 3
Proof for the case of k not divisible by 3 in Theorem 2.9. We now argue how to handle the case when
k mod 3 6= 0 in the statement of Theorem 2.9. Assume k is of the form K + L, where K ≡ 0 (mod 3)
and L = k mod 3 ∈ {1, 2}. We will give a reduction from Max K-Colorable Subgraph, which we already
showed to be NP-hard to approximate within a factor 1 − 1/(33K) + ε, to Max k-Colorable Subgraph.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 422
I MPROVED I NAPPROXIMABILITY R ESULTS FOR M AXIMUM k-C OLORABLE S UBGRAPH
Let GK be an (unweighted) instance of Max K-Colorable Subgraph with M edges. Construct a graph
H by adding L new vertices u1 , . . . , uL to GK . Each ui is connected by an edge of weight dv /K to each
vertex v ∈ V (GK ), where dv is the degree of v in GK . If L > 1, (u1 , u2 ) is an edge in H with weight
M/(33K). The total weight of edges in H equals
2LM M(L − 1)
M0 = M + + .
K 33K
Clearly if GK is K-colorable, then H is k-colorable. For the soundness part, suppose every K-coloring
of GK miscolors at least (1/(33K) − ε)M edges. Let χ be an optimal k-coloring of H. We will prove that
χ miscolors edges with total weight at least (1/(33K) − ε)M. This will certainly be the case if L > 1
and χ(u1 ) = χ(u2 ). So we can assume χ uses L colors for the newly added vertices ui . If χ(v) = χ(ui )
for some v ∈ V (GK ), we can change χ(v) to one of the K colors not used to color {u1 , . . . , uL } so that
the weight of miscolored edges does not increase. Therefore, we can assume that χ uses only K colors
to color the GK portion of H. But this implies at least (1/(33K) − ε)M edges are miscolored by χ, as
desired.
Thus every k-coloring of H miscolors at least a fraction
M(1/(33K) − ε) (1/(33K) − ε) 1
0
= ⩾ −ε
M 1 + 2L/K + (L − 1)/(33K) 33(k + L) + (L − 1)
of the total weight of edges in H. Since L = k mod 3, the bound stated in Theorem 2.9 holds.
3 Conditional hardness results for Max k-Colorable Subgraph
We will first review the 2-to-1 Conjecture, and then construct a noise operator, which allows us to preserve
k-colorability. Then we will bound the stability of coloring functions with respect to this noise operator.
In the last section, we will give a PCP verifier which concludes the hardness result.
3.1 Preliminaries
We begin by reviewing some definitions and the d-to-1 conjecture.
Definition 3.1. An instance of a bipartite Label Cover problem represented as L = (U,V, E,W, RU , RV , Π)
consists of a weighted bipartite graph over node sets U and V with edges e = (u, v) ∈ E of non-negative
real weight we ∈ W . RU and RV are integers with 1 ⩽ RU ⩽ RV . Π is a collection of projection functions
for each edge:
Π = {πvu : {1, . . . , RV } → {1, . . . , RU } u ∈ U, v ∈ V } .
A labeling ` is a mapping ` : U → {1, . . . , RU }, ` : V → {1, . . . , RV }. An edge e = (u, v) is satisfied by the
labeling ` if πe (`(v)) = `(u). We define the value of a labeling as the sum of weights of edges satisfied by
this labeling normalized by the total weight. Opt(L) is the maximum value over any labeling.
Definition 3.2. A projection π : {1, . . . , RV } → {1, . . . , RU } is called d-to-1 if for each i ∈ {1, . . . , RU },
|π −1 (i)| ⩽ d. It is called exactly d-to-1 if |π −1 (i)| = d for each i ∈ {1, 2, . . . , RU }.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 423
V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP
Definition 3.3. A bipartite Label-Cover instance L is called d-to-1 Label-Cover if all projection functions,
π ∈ Π are d-to-1.
The following conjecture was first introduced in a seminal paper by Khot [10]. We use a slight
refinement of it due to Dinur et al. [3].
Conjecture 3.4 (d-to-1 Conjecture, as stated in [3]). For every constant γ > 0, the following decision
problem is NP-hard. Given an exactly d-to-1 Label-Cover instance L with RV = R(γ) and RU = dRV
many labels:
• Yes: Opt(L) = 1,
• No: Opt(L) ⩽ γ.
Using the reductions from [3], it is possible to show that the above conjecture still holds given that
the graph (U ∪V, E) is left-regular and unweighted, i. e., we = 1 for all e ∈ E.
3.2 Noise operators
For a positive integer M, we will denote by [M] the set {0, 1, . . . , M − 1}. We will identify elements of
[M 2 ] with [M] × [M] in the obvious way, with the pair (a, b) ∈ [M]2 corresponding a + Mb ∈ [M 2 ].
Definition 3.5. A Markov operator T is a linear operator which maps probability measures to other
probability measures. In a finite discrete setting, it is defined by a stochastic matrix whose (x, y)’th
entry T (x → y) is the probability of transitioning from x to y. Such an operator is called symmetric if
T (x → y) = T (y → x) = T (x↔y).
Definition 3.6. Given ρ ∈ [−1, 1], the Beckner noise operator, Tρ on [q] is defined as
1 1 1
Tρ (x → x) = + 1− ρ and Tρ (x → y) = (1 − ρ)
q q q
for any x 6= y.
Observation 3.7. All eigenvalues of the operator Tρ are given by
1 = λ0 (Tρ ) ⩾ λ1 (Tρ ) = · · · = λq−1 (Tρ ) = ρ .
Any orthonormal basis α0 , α1 , . . . , αq−1 with α0 being constant vector, is also a basis for Tρ .
Lemma 3.8. For an integer q ⩾ 6, there exists a symmetric Markov operator T on [q]2 whose diagonal
entries are all 0 and with eigenvalues 1 = λ0 ⩾ λ1 ⩾ . . . ⩾ λq2 −1 such that the spectral radius ρ(T ) =
max{|λ1 |, |λq2 −1 |} is at most 4/(q − 1).
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 424
I MPROVED I NAPPROXIMABILITY R ESULTS FOR M AXIMUM k-C OLORABLE S UBGRAPH
Proof. Consider the symmetric Markov operator T on [q]2 such that, for x = (x1 , x2 ), y = (y1 , y2 ) ∈ [q]2 ,
α if {x1 , x2 } ∩ {y1 , y2 } = 0/ and x1 6= x2 , y1 6= y2 ,
β if x 6∈ {y , y } and x = x , y 6= y ,
1 1 2 1 2 1 2
T (x↔y) =
β if y1 6∈ {x1 , x2 } and x1 6= x2 , y1 = y2 ,
0 else,
where
1 1
α= and β= .
(q − 1)(q − 3) (q − 1)(q − 2)
It is clear that T is symmetric and doubly stochastic.
To bound the spectral radius of T , we will bound the second largest eigenvalue λ1 (T 2 ) of T 2 . Notice
that T 2 is also a symmetric Markov operator. Moreover the set of eigenvalues of T 2 , {λi (T 2 )}i is equal
to {λi (T )2 }i . Therefore
λ1 (T 2 ) ⩾ max(λ12 (T ), λq22 −1 (T )) ⩾ ρ(T )2 .
Notice that T 2 (x↔y) > 0 for all pairs x, y ∈ [q]2 . Consider the variational characterization of 1 −
λ1 (T 2 ) [17]:
∑x,y (ψ(x) − ψ(y))2 π(x)T 2 (x↔y) π(x)(ψ(x) − ψ(y))2 T 2 (x↔y)
min ⩾ min min = min q2 T 2 (x↔y)
ψ ∑x,y (ψ(x) − ψ(y))2 π(x)π(y) ψ x,y (ψ(x) − ψ(y))2 π(x)π(y) x,y
where π corresponds to the stationary distribution for Markov operator T 2 .
For any two pairs (x1 , x2 ), (y1 , y2 ) ∈ [q]2 , let l = |[q] \ {x1 , x2 , y1 , y2 }|. Then we have
l(l − 1)β 2 ⩾ (q − 2)(q − 3)β 2 if x1 = x2 and y1 = y2 ,
l(l − 1)αβ ⩾ (q − 3)(q − 4)αβ if x1 6= x2 and y1 = y2 ,
T 2 ((x1 , x2 )↔(y1 , y2 )) =
l(l − 1)αβ ⩾ (q − 3)(q − 4)αβ if x1 = x2 and y1 6= y2 ,
l(l − 1)α 2 + lβ 2 ⩾ (q − 4)((q − 5)α 2 + β 2 ) if x 6= x and y 6= y .
1 2 1 2
(q − 5)(q − 4)
⩾ .
(q − 3)2 (q − 2)(q − 1)
So s
(q − 5)(q − 4)q2 4
q
ρ(T ) ⩽ λ1 (T 2 ) ⩽ 1− 2
⩽ for q ⩾ 6 .
(q − 3) (q − 2)(q − 1) q − 1
3.3 q-ary functions, influences, noise stability
We define inner product on space of functions from [q]N to R as h f , gi = Ex∼[q]N [ f (x)g(x)]. Here x ∼ D
denotes sampling from distribution D and D = [q]N denotes the uniform distribution on [q]N .
Given a symmetric Markov operator T and x = (x1 , . . . , xN ) ∈ [q]N , let T ⊗N x denote the product
distribution on [q]N whose ith entry yi is distributed according to T (xi ↔yi ). Therefore T ⊗N f (x) =
Ey∼T ⊗N x [ f (y)].
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 425
V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP
Definition 3.9. Given x ∈ [q]N and a ∈ [q], let |x|a be the number of coordinates equal to a, a =
|{i | xi = a}|. We will use |x| to denote the number of non-zero coordinates of x, |x| = ∑a6=0 |x|a .
Definition 3.10. Let α0 , α1 , . . . , αq−1 be an orthonormal basis of Rq such that α0 is all constant vector.
N
For x ∈ [q]N , we define αx ∈ Rq as
αx = αx1 ⊗ . . . ⊗ αxN .
Definition 3.11 (Fourier coefficients). For a function f : [q]N → R, define fˆ(αx ) = h f , αx i.
Definition 3.12. Let f : [q]N → R be a function. The influence of ith variable on f , Inf i ( f ) is defined by
Inf i ( f ) = E [Var [ f (x)|x1 , . . . , xi−1 , xi+1 , . . . , xN ]]
where x1 , . . . , xN are uniformly distributed.
Observation 3.13. Inf i ( f ) = ∑x:xi 6=0 fˆ2 (αx ).
Definition 3.14. Let f : [q]N → R be a function. The low-level influence of ith variable of f is defined by
Inf ⩽t
i (f) = ∑ fˆ2 (αx ).
x:xi 6=0, |x|⩽t
Observation 3.15. For every function f : [q]N → R,
∑ Inf ⩽t ˆ2 ˆ2 2
i ( f ) = ∑ f (αx )|x| ⩽ t ∑ f (αx ) = tk f k2 .
i x:|x|⩽t x
If f : [q]N → [0, 1], then k f k22 ⩽ 1, so ∑i Inf ⩽t
i ( f ) ⩽ t.
Definition 3.16 (Noise stability). Let f be a function from [q]N to R, and let −1 ⩽ ρ ⩽ 1. Define the
noise stability of f at ρ as
Sρ ( f ) = h f , Tρ⊗n f i = ∑ ρ |x| fˆi2 (αx )
x
where Tρ is the Beckner operator as in Definition 3.6.
A natural way to think about a q-coloring function is as a collection of q-indicator variables summing
to 1 at every point. To make this formal:
Definition 3.17. Define the unit q-simplex as ∆q = {(x1 , . . . , xq ) ∈ Rq | ∑ xi = 1, xi ⩾ 0}.
Observation 3.18. For positive integers Q, q and any function f = ( f1 , . . . , fq ) : [Q]N → ∆q ,
∑ Inf ⩽t ⩽t 2
i ( f ) = ∑ ∑ Inf i ( f j ) ⩽ t ∑ k f j k ⩽ t .
i i j j
We want to prove a lower bound on the stability of q-ary functions with noise operators T . The
following proposition is generalization of Proposition 11.4 in [11] to general symmetric Markov operators
T with small spectral radii.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 426
I MPROVED I NAPPROXIMABILITY R ESULTS FOR M AXIMUM k-C OLORABLE S UBGRAPH
Definition 3.19. Let ρ ∈ [0, 1] and µ ∈ [0, 1]. Let X and Y denote normal random variables with mean 0
and covariance matrix
1 ρ
.
ρ 1
We define
Λρ (µ) = Prob [X ⩾ t and Y ⩾ t] .
where t is chosen so that Prob[X ⩾ t] = µ.
Following is a restatement of the famous Majority is stablest theorem:
Theorem 3.20 (Majority is Stablest, [11]). Fix q ⩾ 2 and ρ ∈ [0, 1). Then for any ε > 0 there exists
a small enough δ = δ (ε, p, q) > 0 such that if f : [q]n → [0, 1] is any function satisfying E[ f ] = µ and
Inf i ( f ) ⩽ δ for all i = 1, . . . , n then
Sρ ( f ) ⩽ Λρ (µ) + ε.
Proposition 3.21. For integers Q, q ⩾ 3, and a symmetric Markov operator T on [Q] with spectral radius
ρ(T ) ⩽ c/(q − 1), for some c > 0, there exists t = t(q) > 0 and a small enough δ = δ (q) > 0 such that
any function f = ( f1 , . . . , fq ) : [Q]N → ∆q with Inf ⩽t
i ( f ) ⩽ δ , for all i, satisfies
q
∑ h f j , T ⊗N f j i ⩾ 1/q − 2c ln q/q2 −C ln ln q/q2
j=1
for some universal constant C < ∞.
Proof. Let t = 4, fi : [Q]N → [0, 1] denote the ith coordinate function of f , and let µi = E [ fi ]. Let
α0 , . . . , αQ−1 be an orthonormal set of eigenvectors for T with corresponding eigenvalues λ0 ⩾ . . . ⩾ λQ−1 ,
with ρ = ρ(T ) ⩽ c/(q − 1) being the spectral radius of T . Notice that T is symmetric so λ0 = 1 and α0
is a constant vector. Therefore E [ fi ] = fˆi (α0 ) = µi . Then (using the notation from [3]):
|x|
T ⊗N αx = ( ∏ λa a )αx
a6=0
and hence
|x|
T ⊗N fi = ∑( ∏ λa a ) fˆi (αx )αx .
x a6=0
At this point, consider the Beckner operator, Tρ on [Q]. Since α0 is the uniform distribution
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 427
V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP
α0 , α1 , . . . , αQ−1 is also an orthonormal basis for Tρ by Observation 3.7. Thus
|x|
h fi , T ⊗N fi i = fˆi2 (α0 ) − fˆi2 (α0 ) + ∑ ( ∏ λa a ) fˆi2 (αx )
x a6=0
| {z }
⩾ −ρ |x| if |x| 6= 0,
= 1
else.
⩾ 2µi2 − ∑ ρ |x| fˆi2 (αx ) = 2µi2 − ∑ ρ |x| fˆi2 (αx ) − ∑ ρ |x| fˆi2 (αx )
x x:|x|⩽4 x:|x|>4
⩾ 2µi2 − ∑ ρ |x| fˆi2 (αx ) − ρ 4
x:|x|⩽4
⩾ 2µi2 − ∑ ρ |x| fˆi2 (αx ) − q−3 .
x:|x|⩽4
|x|
At this point, let f˜i (x) = ∑x:|x|⩽4 (∏a6=0 λa a ) fˆi (αx )αx be the function having the same low-level coeffi-
cients with fi (x) and 0 for the higher-levels. It is easy to verify that E f˜i = µi , Inf i ( f j ) ⩾ Inf i ( f˜j ) =
Inf ⩽4 ˜ |x| ˆ2 ⩽t ⩽4
i ( f j ) and Sρ ( f j ) = ∑x:|x|⩽4 ρ f i (αx ). In particular, our assumption ∑ j Inf i ( f j ) = ∑ j Inf i ( f j ) ⩽ δ
implies ∑ j Inf i ( f˜j ) ⩽ δ .
Let δ be a small enough constant such that S q−1 c ( f˜i ) ⩽ Λ c (µi ) + ε for some small ε ⩽ 1/q3 , from
q−1
the Majority is Stablest Theorem [12]. Below, for a real x, [x]+ denotes max{x, 0}. Then
∑h fi , T ⊗N fi i ⩾ ∑ 2µi2 − Sρ ( f˜i ) − q−2
i i
h i
2 c ( f˜i ) − q
−2
⩾ 2µ
∑ i q−1− S
i
h i+
⩾ ∑ 2µi2 − Λ c
q−1
(µi ) − 2q−2
i
1 2c ln q ln ln q
⩾ − −O .
q q2 q2
The last inequality is proved in the same way as Proposition 11.4 in [11]. The only difference is that we
have
2 c 2 ln ln q
F(µi ) = µi + 2µ ln(1/µi ) · 1 +C
q−1 i ln q
and
q h i+ q
∑ 2µi2 − Λ q−1c (µi ) ⩾ ∑ (2µi2 − F(µi ))
i=1 i=1
which is convex because µi ⩽ (1/q)1/10 and minimized at µi = 1/q. In this case, we have
q
∑ (2µi2 − F(µi )) ⩾ q q−2 − 2cq−3 ln q(1 +C ln ln q/ ln q
i=1
from which the above claim follows.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 428
I MPROVED I NAPPROXIMABILITY R ESULTS FOR M AXIMUM k-C OLORABLE S UBGRAPH
Definition 3.22 (Moving between domains). For every x = (x1 , . . . , x2N ) ∈ [q]2N , denote x ∈ [q2 ]N as
x = ((x1 , x2 ), . . . , (x2N−1 , x2N )) .
Similarly for y = (y1 , . . . , yN ) ∈ [q2 ]N , denote y ∈ [q]2N as
y = (y1,1 , y1,2 , . . . , yN,1 , yN,2 ) ,
where yi = yi,1 + yi,2 q such that yi,1 , yi,2 ∈ [q]. For a function f on [q]2N , define f on [q2 ]N as f (y) = f (y).
The relationship between influences of variables for functions f and f are given by the following claim
(Claim 2.7 in [3]).
Claim 3.23. For every function f : [q]2N → R, i ∈ {1, . . . , N} and any t ⩾ 1,
Inf ⩽t ⩽2t ⩽2t
i ( f ) ⩽ Inf 2i−1 ( f ) + Inf 2i ( f ) .
3.4 PCP verifier for Max k-Colorable Subgraph
This verifier uses ideas similar to the Max k-Cut verifier given in [11] and the 4-coloring hardness
reduction in [3]. Let L = (U,V, E, R, 2R, Π) be a 2-to-1 bipartite, unweighted and left regular Label-
Cover instance as in Conjecture 3.4. Assume the proof is given as the Long Code over [k]2R of the
label of every vertex v ∈ V . Below for a permutation σ on {1, . . . , n} and a vector x ∈ Rn , x ◦ σ denotes
(xσ (1) , xσ (2) , · · · , xσ (n) ). For a function f on Rn , f ◦ σ is defined as f ◦ σ (x) = f (x ◦ σ ).
• Pick u uniformly at random from U, u ∼ U.
• Pick v, v0 uniformly at random from u’s neighbors. Let π, π 0 be the associated projection functions,
χv , χv0 be the (supposed) Long Codes for the labels of v, v0 respectively.
• Let T be the Markov operator on [k]2 given in Lemma 3.8. Pick x ∼ [k2 ]R and y ∼ T ⊗R x. Let σv , σv0
be two permutations of {1, . . . , 2R} such that
π(σv−1 (2i − 1)) = π(σv−1 (2i)) = π 0 (σv−1 0 −1
0 (2i − 1)) = π (σv0 (2i))
(both π and π 0 are exactly 2-to-1, so such permutations exist).
• Accept iff χv ◦ σv (x) and χv0 ◦ σv0 (y) are different.
Lemma 3.24 (Completeness). If the original 2-to-1 Label-Cover instance L has a labeling which satisfies
all constraints, then there is a proof which makes the above verifier always accept.
Proof. Let ` : V → {1, . . . , 2R} be a labeling for L satisfying all constraints in Π. Pick χv as the Long
Code encoding of `(v). Given any pair of vertices v, v0 ∈ V which share a common neighbor u ∈ U, and
x, y ∈ [k]2R pairs such that
Pr y ∼ T ⊗R (x) = ∏ T ((x2i−1 , x2i )↔(y2i−1 , y2i )) > 0 ,
i
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 429
V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP
let π, π 0 be the projection functions and σv , σv0 be the permutations as defined in the description of the
verifier. We have χv (x ◦ σv ) = xσ (`(v)) and χv0 (y ◦ σv0 ) = yσ 0 (`(v0 )) . Since π(`(v)) = π 0 (`(v0 )), this
implies σv (`(v)), σv0 (`(v0 )) ∈ {2i − 1, 2i} for some i ⩽ R. But
T ((x2i−1 , x2i )↔(y2i−1 , y2i )) > 0 =⇒ {x2i−1 , x2i } ∩ {y2i−1 , y2i } = 0/ ,
therefore χv ◦ σv (x) = xσv (`(v)) 6= yσv0 (`(v0 )) = χv0 ◦ σv0 (y). So the verifier always accepts.
Lemma 3.25 (Soundness). There is a constant C such that, if the above verifier passes with probability
exceeding 1 − 1/k + O(ln k/k2 ), then there is a labeling of L which satisfies γ 0 = γ 0 (k) fraction of the
constraints independent of label set size R.
Proof. For each node v ∈ V , let f v : [k]2R → ∆k be the function f v (x) = eχv (x) where ei is the indicator
vector of the ith coordinate. Let Γ(u) denote the set of vertices adjacent to u in the Label Cover graph.
After arithmetizing, we can write the verifier’s acceptance probability as
h i
0
Pr [acc] = Eu,v,v0 1 − ∑ j h f jv ◦ σv , T ⊗R ( f jv ◦ σv0 )i
h h ii
0
= 1 − Eu ∑ j Ev,v0 h f jv ◦ σv , T ⊗R ( f jv ◦ σv0 )i
h h i h ii
0
= 1 − Eu ∑ j hEv f jv ◦ σv , T ⊗R Ev0 f jv ◦ σv0 i
h i h i
= 1 − Eu ∑ j hguj , T ⊗R guj i guj = Ev∼Γ(u) f jv ◦ σv
⩾ 1 − 1/k +C ln k/k2
where gu : [k2 ]R → ∆k and some constant C. By averaging, for at least a fraction δ = (ε/2) ln k/k2 of
vertices in U, we have
∑hguj , T ⊗R guj i ⩽ 1/k −C ln k/k2 .
j
Let these be “good” vertices. For a good vertex, by Proposition 3.21, there exist constants δ = δ (k),
t = t(k) and i such that Inf ⩽t u
i (g ) ⩾ δ . Let
Suggu = {i | i ∈ {1, . . . , R} ∧ Inf ⩽t u
i (g ) ⩾ δ } ,
so |Suggu | ⩾ 1. By Observation 3.18, |Suggu | ⩽ t/δ . For a good vertex u, and j ∈ Suggu :
h i
δ ⩽ Inf ⩽t
j (g u
) = Ev∼Γ(u) Inf ⩽t
j f v ◦σ
v
Therefore, for at least a fraction δ /2 of neighbors v of u, Inf ⩽t v
j ( f ◦ σv ) ⩾ δ /2. For such v and j, by
Claim 3.23,
Inf ⩽2t v ⩽2t v
2 j−1 ( f ◦ σv ) + Inf 2 j ( f ◦ σv ) ⩾ δ /2 .
Therefore for some j ∈ [2R], Inf ⩽2t v
j ( f ) ⩾ δ /4. Let
Suggv = { j | j ∈ {1, . . . , 2R} ∧ Inf ⩽2t v
j ( f ) ⩾ δ /4} .
Again, Suggv is not empty and |Suggv | ⩽ 8t/δ .
Following the decoding procedure in [11], we deduce that it is possible to satisfy a fraction γ 0 =
γ (δ ,t) = γ 0 (k) of the constraints.
0
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 430
I MPROVED I NAPPROXIMABILITY R ESULTS FOR M AXIMUM k-C OLORABLE S UBGRAPH
Note that our PCP verifier makes “k-coloring” tests. By the standard conversion from PCP verifiers to
CSP hardness, and Remark 2.6 about conversion to unweighted graphs with the same inapproximability
factor, we conclude the main result of this section by combining Lemmas 3.24 and 3.25.
Theorem 3.26. For every constant k ⩾ 3, assuming the 2-to-1 Conjecture, it is NP-hard to approximate
Max k-Colorable Subgraph within a factor of 1 − 1/k + O(ln k/k2 ).
A Details about “tripartite" PCP
We now briefly discuss the (minor) changes in analysis needed to make the PCP in [6] have the prop-
erties claimed in Remark 2.5. The discussion assumes substantial familiarity with Håstad-style PCP
constructions [8], and is intended as an aid for an expert to check our claim.
The crux in PCP constructions is a procedure to test that two tables A, B are the legal long code
encodings of two labels a, b which satisfy some projection constraint π(b) = a. (In the overall construction,
this projection constraint is between two nodes u, v of a Label Cover instance, and A, B supposedly encodes
labels to u, v respectively.) Here π : [M] → [N], where we denote [m] = {1, 2, . . . , m}, A : FN → {1, −1}
and B : FM → {1, −1} with Fm denoting the set of Boolean functions [m] → {1, −1}. (It is convenient to
use ±1 to denote truth values, with −1 being true.) We say A is the long code of a ∈ [N] if A( f ) = f (a)
for all f ∈ FN , and similarly for B being the long code of b ∈ [M]. Note that a long code has the following
“folded” property: A(− f ) = −A( f ). We can assume that the tables A, B are folded, by inferring the value
A(− f ) from the value A( f ) for half the functions.
The specific nature of the test must correspond to the predicate of the CSP for which inapproximability
is sought. Specifically, for the PCP of [6], which checks the predicate
(A( f ) ∨ (B(g) = B(g1 )) ∧ (A( f ) ∨ (B(g) = B(g2 )) , (A.1)
one would pick functions f , g, g1 , g2 such that for (a, b) ∈ [N] × [M] with π(b) = a, we have
(( f (a) = 1) =⇒ (g(b) = g1 (b))) ∧ (( f (a) = −1) =⇒ (g(b) = g2 (b))) .
This would ensure that the test has perfect completeness, i. e., accepts A, B which are long codes of a, b
with π(b) = a with probability 1. The actual test picks f , g randomly, and defines g1 = ( f ◦ π ∧ h)g and
g2 = (− f ◦ π ∧ h0 )g for functions h, h0 being independent samples from some suitable distribution. It is
easy to see that the perfect completeness of the test holds for any choice of h.h0 . The soundness claim
relies on picking h, h0 according to a carefully chosen distribution (see [6] or [8] for details), which in
particular sets those functions to −1 at each point with probability close to 1.
We note that the foldedness of A, B will imply negations in the constraint (A.1) above.
The structure of the soundness analysis in [6], which in fact is essentially identical to the analysis for
the PCP for satisfiable Max 3SAT from [8], is as follows. Assuming that the test accepts with probability
at least 1/2 + ε, one shows how to decode A and B into labels a and b respectively such that π(b) = a
holds with probability ε1 (ε) > 0. When combined with the hardness of Label Cover, such a decoding
procedure immediately implies the construction of a PCP with soundness 1/2 + ε, which in turn implies
the inapproximability of satisfying a 1/2 + ε fraction constraints of a satisfiable instance of the associated
CSP.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 431
V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP
The change we make to the PCP in [6] is to make the queries g1 , g2 into a C-table, that is distinct from
B and further is not assumed to be folded. Note that the perfect completeness of the test is maintained, as
one can simply choose C = B (or to be precise, the unfolded version of table B). Let us turn to how the
soundness analysis is affected.
The probability that the test (A.1) accepts (when the queries B(gi ) are replaced by C(gi )) can be
arithmetized as follows:
1 + A( f ) 1 − B(g)C(g1 ) 1 − A( f ) 1 − B(g)C(g2 )
1 − E f ,g,g1 ,g2 + .
2 2 2 2
Using the fact that A is folded (so A(− f ) = −A( f ) and E f [A( f )] = 0), and the distribution of ( f , g, g2 )
is identical to that of (− f , g, g1 ), the above expression simplifies to
1 1 1
+ E f ,g,g1 [B(g)C(g1 )] + E f ,g,g1 [A( f )B(g)C(g1 )] .
2 2 2
The analysis in [8, Thm. 6.5] upper bounds E[B(g)B(g1 )] by ε. Actually, this is not done for a fixed A
table, but rather when expectation is also taken over the projection π corresponding to a random neighbor
u of the node v whose label B is encoding. This part of the analysis is not affected by the change to a
C-table, so we ignore this complication in the description here.
The analysis proceeds by expanding E[B(g)B(g1 )] by Fourier analysis and upper bounds
(−1)sx + (1 − 2ε)sx
∑ B̂2β ∏ 2
(A.2)
β x∈π(β )
where sx = |π −1 (x) ∩ β | (this is eq. (36) in [8]). To bound (A.2), Håstad proceeds by dividing the sum
into three parts, small |β |, medium |β |, and large |β | (see Lemma 6.7 of [8]). The sum for small and
large sized β is bounded by a small δ , and the contribution of the medium terms is amortized over the
different choices of the bias in the distribution of the function h in the choice of g1 . We can mimic his
analysis essentially verbatim: the only change we need to do is replace B̂2β by |B̂β ||Ĉβ |. In the analysis of
the medium and large |β | terms, wherever Håstad uses the upper bound ∑β B̂2β ⩽ 1 in the analysis, we
can instead use ∑β |B̂β ||Ĉβ | ⩽ 1 which follows from Parseval’s identity and Cauchy-Schwarz inequality.
The bound for small β (Lemma 6.8 in [8]) uses the fact that terms with even |β | contribute 0 to (A.2)
by virtue of B being folded. This remains true for us—even though C may not be folded, for |B̂β ||Ĉβ |
to be nonzero, we must have |β | to be odd as B is still folded. Thus, in the end, we can upper bound
E[B(g)C(g1 )] by the same bound Håstad got for E[B(g)B(g1 )].
Let us now turn to the E[A( f )B(g)C(g1 )] term. Once again the analysis is similar to that of the
E[A( f )B(g)B(g1 )] term in [8], where it is shown that if E[A( f )B(g)B(g1 )] ⩾ δ , then one can decode
labels a, b such that π(b) = a with probability δ1 = δ1 (δ ) > 0. For us, using Fourier expansion the
assumption E[A( f )B(g)C(g1 )] ⩾ δ gives
h i
E ∑ Âα B̂β Ĉβ p(α, β ) ⩾ δ ,
β ,α⊆π(β )
similar to Equation (42) of [8] (where p(α, β ) is also defined). The only change compared to [8] is
that B̂β Ĉβ replaces B̂2β . One can check that the rest of the analysis in the proof of Lemma 6.11 of [8]
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 432
I MPROVED I NAPPROXIMABILITY R ESULTS FOR M AXIMUM k-C OLORABLE S UBGRAPH
goes through unaltered if we replace B̂2β by |B̂β ||Ĉβ | everywhere. Once again all uses of the key fact
∑β B̂2β ⩽ 1 can be replaced by the valid inequality ∑β |B̂β ||Ĉβ | ⩽ 1. A minor change we make in the
decoding procedure is that the “clause prover” P1 picks a random subset β with probability proportional
to |B̂β ||Ĉβ | instead of probability equal to B̂2β , and then returns a random y ∈ β . As the B-table is folded,
we have B̂0/ = 0, and so the decoding procedure will always pick a nonempty β and is thus well defined.
Since ∑β |B̂β ||Ĉβ | ⩽ 1, the probability of picking β is at least |B̂β ||Ĉβ |, so replacing B̂2β by |B̂β ||Ĉβ | still
gives a lower bound on the success of the label-decoding procedure, which is what we seek.
Thus, with these changes we can complete the soundness analysis of the tripartite PCP where the B
table is split into two tables B and C, and without requiring the C table to be folded (though we necessarily
require the B table to be folded). This gives the PCP underlying the inapproximability result claimed in
Proposition 2.4.
References
[1] P ER AUSTRIN , RYAN O’D ONNELL , L I -YANG TAN , AND J OHN W RIGHT: New NP-hardness
results for 3-coloring and 2-to-1 label cover. Technical report, 2012. Preliminary version in
APPROX’12. [arXiv:1210.5648] 416, 420
[2] P IERLUIGI C RESCENZI , R ICCARDO S ILVESTRI , AND L UCA T REVISAN: On weighted vs un-
weighted versions of combinatorial optimization problems. Inform. and Comput., 167(1):10–26,
2001. Preliminary version in 4th ISTCS, 1996. [doi:10.1006/inco.2000.3011] 418
[3] I RIT D INUR , E LCHANAN M OSSEL , AND O DED R EGEV: Conditional hardness for approxi-
mate coloring. SIAM J. Comput., 39(3):843–873, 2009. Preliminary version in STOC’06.
[doi:10.1137/07068062X] 415, 424, 427, 429
[4] A LAN M. F RIEZE AND M ARK J ERRUM: Improved approximation algorithms for MAX k-CUT
and MAX BISECTION. Algorithmica, 18(1):67–81, 1997. Preliminary version in IPCO’95.
[doi:10.1007/BF02523688] 414
[5] V ENKATESAN G URUSWAMI: Inapproximability results for set splitting and satisfiability problems
with no mixed clauses. Algorithmica, 38(3):451–469, 2004. Preliminary version in APPROX’00.
[doi:10.1007/s00453-003-1072-z] 417
[6] V ENKATESAN G URUSWAMI , DANIEL L EWIN , M ADHU S UDAN , AND L UCA T REVISAN: A tight
characterization of NP with 3 query PCPs. In Proc. 39th FOCS, pp. 8–17. IEEE Comp. Soc. Press,
1998. [doi:10.1109/SFCS.1998.743424] 415, 416, 417, 431, 432
[7] V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP: Improved inapproximability results for max-
imum k-colorable subgraph. In Proc. 12th Internat. Workshop on Approximation Algorithms for Com-
binatorial Optimization Problems (APPROX’09), pp. 163–176. Springer, 2009. [doi:10.1007/978-3-
642-03685-9_13] 413
[8] J OHAN H ÅSTAD: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Prelimi-
nary version in STOC’97. [doi:10.1145/502090.502098] 417, 431, 432
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 433
V ENKATESAN G URUSWAMI AND A LI K EMAL S INOP
[9] V IGGO K ANN , S ANJEEV K HANNA , J ENS L AGERGREN , AND A LESSANDRO PANCONESI: On
the hardness of approximating MAX k-CUT and its dual. Chicago J. Theor. Comput. Sci., 1997(2),
1997. CJTCS. Preliminary version in ISTCS’96. 415, 420, 422
[10] S UBHASH K HOT: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp.
767–775. ACM Press, 2002. [doi:10.1145/509907.510017] 424
[11] 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 2-variable CSPs? SIAM J. Comput., 37(1):319–
357, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447372] 414, 426, 427,
428, 429, 430
[12] E LCHANAN M OSSEL , RYAN O’D ONNELL , AND K RZYSZTOF O LESZKIEWICZ: Noise stability
of functions with low influences: invariance and optimality. Ann. of Math., 171(1):295–341, 2010.
Preliminary version in FOCS’05. [doi:10.4007/annals.2010.171.295] 415, 428
[13] RYAN O’D ONNELL AND Y I W U: Conditional hardness for satisfiable 3-CSPs. In Proc. 41st STOC,
pp. 493–502. ACM Press, 2009. [doi:10.1145/1536414.1536482] 416
[14] C HRISTOS H. PAPADIMITRIOU AND M IHALIS YANNAKAKIS: Optimization, approximation, and
complexity classes. J. Comput. System Sci., 43(3):425–440, 1991. Preliminary version in STOC’88.
[doi:10.1016/0022-0000(91)90023-X] 414
[15] E REZ P ETRANK: The hardness of approximation: Gap location. Comput. Complexity, 4(2):133–157,
1994. Preliminary version in ISTCS’93. [doi:10.1007/BF01202286] 414, 415, 416
[16] P RASAD R AGHAVENDRA: Optimal algorithms and inapproximability results for every CSP? In
Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414] 416
[17] A LISTAIR S INCLAIR: Improved bounds for mixing rates of Markov chains and multicommod-
ity flow. Combin. Probab. Comput., 1(4):351–370, 1992. Preliminary version in LATIN’92.
[doi:10.1017/S0963548300000390] 425
AUTHORS
Venkatesan Guruswami
Associate professor
Carnegie Mellon University, Pittsburgh, PA
guruswami cmu edu
http://www.cs.cmu.edu/~venkatg
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 434
I MPROVED I NAPPROXIMABILITY R ESULTS FOR M AXIMUM k-C OLORABLE S UBGRAPH
Ali Kemal Sinop
Postdoctoral Research Associate
Princeton University, Princeton, NJ
asinop cs cmu edu
http://www.cs.cmu.edu/~asinop
ABOUT THE AUTHORS
V ENKATESAN G URUSWAMI, or Venkat, as his colleagues call him, received his Bachelor’s
degree from the Indian Institute of Technology at Madras in 1997. He is grateful to
his undergraduate research advisor C. Pandu Rangan for initiating him to the joys of
theoretical computer science. Venkat received his Ph. D. from the Massachusetts Institute
of Technology in 2001. He was fortunate to be advised by Madhu Sudan, with whom he
enjoyed collaboration on a number of topics, most notably on list decoding.
Since 2008, Venkat has been on the faculty of the Computer Science Department at
Carnegie Mellon University. Earlier, he was a faculty member at the University of
Washington. Venkat was a Miller Research Fellow at UC Berkeley during 2001-02,
and was a member of the School of Mathematics, Institute for Advanced Study during
2007-08.
Venkat is interested in several topics in theoretical computer science, including algorith-
mic and algebraic coding theory, approximability of fundamental optimization problems,
pseudorandomness, probabilistically checkable proofs, computational complexity theory,
and algebraic algorithms.
Venkat currently serves on the editorial boards of the SIAM Journal on Computing, IEEE
Transactions on Information Theory, and the ACM Transactions on Computation Theory.
He was recently program committee chair for the 2012 Computational Complexity
conference. Venkat is a recipient of the Presburger award, Packard Fellowship, Sloan
Fellowship, NSF CAREER award, ACM’s Doctoral Dissertation Award, and the IEEE
Information Theory Society Paper Award.
In his (sadly limited) spare time, Venkat enjoys traveling, ethnic vegetarian food, racquet
sports, hiking/running within his humble limits, and listening to Carnatic music.
A LI K EMAL S INOP received his Bachelor’s degree from Bilkent University, Turkey in 2004
and his Master’s degree from the University of Pennsylvania in 2005. He worked at
Siemens Corporate Research from 2005 to 2007. He obtained his Ph. D. from C. M. U.
in 2012; his advisor was Venkatesan Guruswami. His thesis focused on the use of
semi-definite programming hierarchies for various graph partitioning problems. During
2012–2013, he was a postdoc at the Center for Computational Intractability, Princeton
University. He will be a postdoc at the School of Mathematics, Institute for Advanced
Study during 2013–2014. His current research interests are in the use of convex relaxation
hierarchies for basic graph partitioning problems.
T HEORY OF C OMPUTING, Volume 9 (11), 2013, pp. 413–435 435