ECE 650, Fall 2019, Section 01
A Polynomial-Time Reduction from VERTEX-COVER to CNF-SAT
A vertex cover of a graph G = (V, E) is a subset of vertices C ⊆ V such that each edge in E is
incident to at least one vertex in C.
VERTEX-COVER is the following problem:
• Input: An undirected graph G = (V, E), and an integer k ∈ [0, |V |].
• Output: True, if G has a vertex cover of size k, false otherwise.
CNF-SAT is the following problem:
• Input: a propositional logic formula, F , in Conjunctive Normal Form (CNF).
That is, F = c1 ∧ c2 ∧ . . . ∧ cm , for some positive integer m. Each such ci is called a “clause”.
A clause ci = li,1 ∨ . . . ∨ li,p , for some positive integer p. Each such li,j is called a “literal.” A
literal li,j is either an atom, or the negation of an atom.
• Output: True, if F is satisfiable, false otherwise.
We present a polynomial-time reduction from VERTEX-COVER to CNF-SAT. A polynomial-time
reduction is an algorithm that runs in time polynomial in its input. In our case, it takes as input
G, k and produces a formula F with the property that G has a vertex cover of size k if and only if
F is satisfiable.
The use of such a reduction is that given an instance of VERTEX-COVER that we want to
solve, (G, k), we use the reduction to transform it to F , and provide F as input to a SAT solver.
The true/false answer from the SAT solver is the answer to the instance of VERTEX-COVER.
Assuming the SAT solver works efficiently (for some characterization of “efficient”), we now have
an efficient way of solving VERTEX-COVER. Furthermore, the satisfying assignment from the SAT
solver can be used to re-construct the solution to VERTEX-COVER.
The reduction
Given a pair (G, k), where G = (V, E), denote |V | = n. Assume that the vertices are named 1, . . . , n.
Construct F as follows.
• The reduction uses n × k atomic propositions, denoted xi,j , where i ∈ [1, n] and j ∈ [1, k]. A
vertex cover of size k is a list of k vertices. An atomic proposition xi,j is true if and only if the
vertex i of V is the jth vertex in that list.
• The reduction consists of the following clauses
– At least one vertex is the ith vertex in the vertex cover:
∀i ∈ [1, k], a clause (x1,i ∨ x2,i ∨ · · · ∨ xn,i )
– No one vertex can appear twice in a vertex cover.
∀m ∈ [1, n], ∀p, q ∈ [1, k] with p < q, a clause (¬xm,p ∨ ¬xm,q )
In other words, it is not the case that vertex m appears both in positions p and q of the
vertex cover.
– No more than one vertex appears in the mth position of the vertex cover.
∀m ∈ [1, k], ∀p, q ∈ [1, n] with p < q, a clause (¬xp,m ∨ ¬xq,m )
– Every edge is incident to at least one vertex in the vertex cover.
∀hi, ji ∈ E, a clause (xi,1 ∨ xi,2 ∨ · · · ∨ xi,k ∨ xj,1 ∨ xj,2 ∨ · · · ∨ xj,k )
The number of clauses in the reduction is k + n k2 + k n2 + |E|.
