PCPs and Inapproxiability CIS 6930 Sep 17th, 2009
Hardness of Vertex Cover and Steiner tree problem
Lecturer: Dr. My T. Thai Scribe: Nam Nguyen
1 Hardness of Vertex Cover problem
In this section, we denote
• VC(d) the restriction of the cardinality Vertex Cover problem to instances
in which each vertex has degree at most d.
• MAX-3SAT(d) the restriction of MAX-3SAT to Booldean formulae in
which each variable occurs at most d times.
Theorem 29.13
There is a gap-preserving reduction from MAX-3SAT(29) to VC(30) that trans-
forms a Boolean formula φ to a graph G = (V,E) such that
• If OPT (φ) = m, then OPT (G) ≤ 2
3
|V |, and
• If OPT (φ) < (1− �b)m, then OPT (G) > (1 + �v) 23 |V | where �v =
�b
2
Proof:
In order to prove this Theorem, we need to construct a transformation between
instances of MAX-3SAT(29) and VC(30), or, in other words, we need to trans-
form a Boolean formula φ of MAX-3SAT(29) to a graph G = (V,E) of VC(30)
in such a way that the two conditions above will follow. Without loss of gen-
erality, we can assume that φ has m clauses of exactly 3 literals in CNF form
each. Below is the construction of an instance G=(V,E) from φ
1. Let each literal in φ be a vertex in V.
2. For each clause, G has 3 edges connecting its 3 vertices, and
For any u, v ∈ V, if u and v are negations of each other, there will be an
edge connecting u and v.
For example, the Boolean formula φ = (x1 ∨ x̄2 ∨ x3) ∧ (x̄1 ∨ x2 ∨ x3) has the
corresponding graph G as depicted in Figure 1. Besides, using this standard
construction, we observe that
• φ has m clauses of exactly 3 literals each and a literal has a corresponding
verex in V. Thus V has exactly 3m vertices (|V | = 3m).
Hardness of Vertex Cover and Steiner tree problem-1
Figure 1: The graph constructed by φ = (x1 ∨ x̄2 ∨ x3) ∧ (x̄1 ∨ x2 ∨ x3)
• Each vertex in G has 2 edges of type #1 and at most 28 edges of type #2.
Therefore, the vertex degree is at most 30.
• Any Maximum Independent Set (MIS) in G has size at most m (since it
can pick up at most a vertex in each “triangle”).
Showing directly this construction carries the two inequalitis is difficult, we
should show that via the MIS (since the minimum vertex cover is the comple-
ment of the MIS). In particular, we’ll show that the size of a MIS is percisely
OPT(φ). (≥) Condsider the optimal assignment for φ, i.e. the assignment sat-
isfies OPT(φ) clauses. We then pick a satisfied literal from each clause and
consider the set of corresponding verices in G. That set is an independet set
of G (since every vertex is satisfied, there would not be an edge of type #2
connecting any pair of them) and its size is not bigger than the MIS, which
implies OPT (φ) ≤ |I|. (≤) Conversely, let I be an independet set of G, we
show that |I| ≤ OPT (φ). Setting all literals corresponding to I true will give an
assignment that satisfies at least |I| clauses, and of course, this number should
not exceed the maximum satified clauses OPT(φ): |I| ≤ OPT (φ). Now,
• If OPT(φ) = m, i.e, a MIS of G has size of m, then OPT (G) = 2m ≤ 2
3
|V |.
• If OPT (φ) < (1− �b)m, then OPT (G) > 3m− (1− �b)m = (1 + �b2 )
2
3
|V |.
Hence, we can not hope to have an approximation algorithm for
VC(30) with an approximation guarantee of (1+ �b
2
), assuming P 6= NP
Question: Do we really need the two numbers 29 and 30 in this problem? Will
the proof still valid without these numbers?
2 Hardness of Steiner Tree problem
Theorem 29.14
There is a gap preserving reduction from VC(30) to the Steiner tree problem.
It transforms an instance G(V,E) of VC(30) to an instance H = (R,S,cost) of
Steiner tree, where R and S are required and Steiner vertices of H, and cost is
a metric in R. It satisfies:
• If OPT (G) ≤ 2
3
|V |, then OPT (H) ≤ |R|+ 2
3
|S| − 1, and
• If OPT (G) > (1 + �v) 23 |V |, then OPT (H) > (1 + �s)
(
|R|+ 2
3
|S| − 1
)
Hardness of Vertex Cover and Steiner tree problem-2
where �s =
4�v
97
Proof:
We need to construct a transformation from a graph G=(V,E) of VC(30) to a
graph H=(R,S,cost) in such a way that G has a vertex cover of size c if and
only if H has a Steiner tree of cost |R|+ c− 1. If such transformation exists, we
would be able to prove the two proposed inequalities.
Contructing the transformation
Input: A graph G=(V,E)
Output: A graph H=(R,S,cost) where cost is a weight function on edges.
1. For any edge e in E, there is a corresponding vertex re in R. (|R| = |E| )
2. For any vertex v in V, there is a corresponding vertex sv in S. (|S| = |V |)
3. For any re, re′ ∈ R, there is an edge connects them with cost(re, re′) = 2.
4. For any sv, sv′ ∈ S, there is an edge connects them with cost(sv, sv′) = 1.
5. For any re ∈ R and sv ∈ S, there is an edge connects them with cost
cost(re, sv) = 1 if e is incident to v in G.
6. For any re ∈ R and sv ∈ S, there is an edge connects them with cost
cost(re, sv) = 2 if e is not incident to v in G.
Claim: Using the above transformation, G has a Vertex Cover of size
c iff H has a Steiner tree of size |R|+ c− 1
(⇒) Suppose that G has a Vertex Cover VC of size c. Creat a graph G’ whose
vertice are in {sv|v ∈ V C} ∪ {re|e ∈ E} and whose edges are those of cost 1 in
G. Clearly, G’ has |E|+ c = |R|+ c nodes. Moreover, G’ is connected since any
sv and sv′ are connected (#4) and any re is connected to some sv (for VC is
a vertex cover in G, any edge in E must incident to at least a vertex in VC).
Therefore, any spanning tree of G’ will be a Steiner tree for H (since it covers
R ∪ V C) and has cost of |R|+ c− 1.
(⇐) Assume that H has a Steiner tree T of cost |R| + c − 1, we show that G
has a Vertex Cover VC of size c. What we hope to have is a Steiner tree with
all unit cost edges; however, T may contain edges with cost 2 at the beginning.
Therefore, we need to modify T so that it has no edge of cost 2. The following
procedure does the job: (For notation convention, we denote [v] and [u,v] the
nodes in H corresponding to v ∈ V and (u,v) ∈ E in G)
1. If T contains an edge of cost 2 connecting [w] and [u,v], we remove this
edge and add two new edges ([w], [u]) and ([u], [u,v]).
2. If T contains an edge of cost 2 connecting [u,v] and [v,w], we remove this
edge and add two new edges ([u,v], [v]) and ([v], [v,w]).
3. If T contains and edge of cost 2 connecting [u,v] and [w,z] then removing
this arc in T will result in partitioning E into two subsets. Since G is
connected, there must be two edges on different sides of the partition that
share an enpoint. Let they be (x,y) and (y,t). We then connect ([x,y], [y])
and ([y], [y,t]).
Hardness of Vertex Cover and Steiner tree problem-3
Figure 2: Illustration of modifyding Steiner tree T case (1), (2) and (3)
An illustration for the above procedure is presented in Figure 2. Since the
proposed procedure neither disconnects T nor increases its cost, T is still a
Steiner tree of H with cost |R| + c − 1 containing only unit edges. Clearly, T
must span |R|+c nodes including the required set R, and thus, T covers c nodes
in S. We show that this set VC of c vertices is a Vertex Cover in G. This is true
because any vertex [u,v] is connected to the T by an edge of cost 1, which means
that either [u] or [v] is in the tree, i.e, either u or v is in VC. Therefore, VC is
a Vertex Cover in G and
• If OPT (G) ≤ 2
3
|V |, then OPT (H) ≤ |R|+ 2
3
|S| − 1
• If OPT (G) > (1 + �v) 23 |V |, then OPT (H) > |R|+ (1 + �v)
2
3
|S| − 1
Hence, we can not hope to have an approximation algorithm for
Steiner tree problem with an approximation ratio of (1 + �), for a
constant �, assuming P 6= NP
Question: Again, can we ignore the number 30 and just simply use VERTEX-
COVER for the transformation? How can we prove the last inequality, that is
OPT (H) > (1 + �s)
(
|R|+ 2
3
|S| − 1
)
References
[1] V.V. Vazirani, Approximation Algorithms, Springer, 2001.
[2] Professor Lucas Trevisan, Lecture notes 3 and 4 in CS294, UC Berkeley,
2006.
Hardness of Vertex Cover and Steiner tree problem-4