Polynomial-Time Reductions and the 3-SAT to Vertex Cover Reduction

This section explains three central ideas in computational complexity:

1. What a polynomial-time reduction is.
2. How reductions establish that a problem is NP-complete.
3. How to transform an instance of 3-SAT into an equivalent instance of Vertex Cover.

The key principle is that a reduction transfers computational difficulty from one problem to another. If problem $A$ can be transformed efficiently into problem $B$, then an efficient algorithm for $B$ would also yield an efficient algorithm for $A$.

A standard polynomial-time many-one reduction is written

$$A \leq_p B.$$

This means that there is a polynomial-time computable function $f$ such that, for every input $x$,

$$x \in A \iff f(x) \in B.$$

The transformation must preserve the answer exactly: yes-instances map to yes-instances, and no-instances map to no-instances.

Footnotes

1. Cook–Levin theorem - Background on SAT, 3-SAT, and the foundational NP-completeness result. ↩

2. P-time reducibility lecture notes - Definitions of polynomial-time reductions, NP-hardness, and NP-completeness. ↩

(i) What Is Polynomial-Time Reduction?

Consider two decision problems, $A$ and $B$. We say that $A$ is polynomial-time reducible to $B$, written $A \leq_p B$, if an algorithm can convert every instance $x$ of $A$ into an instance $f(x)$ of $B$ in polynomial time, while preserving the answer:

$$x \text{ is a yes-instance of } A \iff f(x) \text{ is a yes-instance of } B.$$

The function $f$ is called the reduction function.

Important properties

• Efficient construction: $f(x)$ must be computable in polynomial time.
• Answer preservation: $x$ and $f(x)$ must have the same yes/no answer.
• Single target instance: A many-one reduction creates one instance of $B$.
• Polynomial growth: The output size must be polynomial in the input size.
• Algorithmic implication: If $B$ has a polynomial-time algorithm, then $A$ also has one.

Suppose $|x|=n$, the reduction takes $O(n^c)$ time, and problem $B$ can be solved in $O(m^d)$ time on an instance of size $m$. If the reduction produces $m \leq n^k$, then solving $A$ through $B$ takes at most

$$O(n^c) + O((n^k)^d) = O(n^c+n^{kd}),$$

which is polynomial in $n$.

Reduction versus ordinary algorithm

A reduction is not necessarily a direct solution to the original problem. Instead, it translates the original problem into another problem whose structure or difficulty is already understood.

For example:

$$\text{3-SAT instance} \longrightarrow \text{Vertex Cover instance}.$$

The reduction is useful only if the following equivalence holds:

$$\varphi \text{ is satisfiable} \iff (G_\varphi,k) \text{ has a vertex cover of size at most } k.$$

Footnotes

1. P-time reducibility lecture notes - Definitions of polynomial-time reductions, NP-hardness, and NP-completeness. ↩

(ii) How Polynomial-Time Reductions Prove NP-Completeness

A decision problem is in NP if a proposed solution, called a certificate, can be checked in polynomial time.

A problem is NP-hard if every problem in NP reduces to it:

$$\forall A \in \mathrm{NP},\quad A \leq_p B.$$

A problem is NP-complete exactly when it satisfies both conditions:

$$B \in \mathrm{NP} \quad\text{and}\quad B \text{ is NP-hard}.$$

Standard proof pattern

To prove that a problem $B$ is NP-complete:

1. Show that $B \in \mathrm{NP}$.
2. Choose a known NP-complete problem $A$.
3. Construct a polynomial-time reduction $A \leq_p B$.
4. Prove the equivalence $$x \in A \iff f(x) \in B.$$
5. Conclude that $B$ is NP-hard.
6. Combine membership and hardness to conclude that $B$ is NP-complete.

The Cook–Levin theorem establishes SAT, and consequently 3-SAT, as a foundational NP-complete problem. Many later NP-completeness proofs use 3-SAT as the source problem.

Why the reduction proves hardness

Assume that $A$ is NP-complete and that

$$A \leq_p B.$$

If $B$ had a polynomial-time algorithm, then an instance of $A$ could be solved by:

1. Applying the polynomial-time reduction to obtain $f(x)$.
2. Running the polynomial-time algorithm for $B$.
3. Returning the same answer.

Thus $A$ would be in P. Since every problem in NP reduces to $A$, this would imply

$$\mathrm{P}=\mathrm{NP}.$$

Therefore, $B$ is at least as difficult as the known NP-complete problem $A$ under polynomial-time reductions.

Footnotes

1. Introduction to Theoretical Computer Science: NP, NP Completeness, and the Cook–Levin Theorem - Formal discussion of NP verification and reductions. ↩

2. Cook–Levin theorem - Background on SAT, 3-SAT, and the foundational NP-completeness result. ↩

3. P-time reducibility lecture notes - Definitions of polynomial-time reductions, NP-hardness, and NP-completeness. ↩

(iii) Reducing 3-SAT to Vertex Cover

Source problem: 3-SAT

An instance of 3-SAT is a Boolean formula in conjunctive normal form:

$$\varphi = C_1 \land C_2 \land \cdots \land C_m,$$

where each clause contains exactly three literals. For example,

$$\varphi = (x_1 \lor \neg x_2 \lor x_3) \land (\neg x_1 \lor x_2 \lor x_4).$$

The question is whether there exists a truth assignment satisfying every clause.

A literal is either $x_i$ or $\neg x_i$. A clause is satisfied if at least one of its literals is true.

Let:

• $n$ be the number of variables;
• $m$ be the number of clauses.

Target problem: Vertex Cover

Given an undirected graph $G=(V,E)$ and an integer $k$, the Vertex Cover problem asks whether there is a set

$$S \subseteq V$$

such that

$$|S| \leq k$$

and every edge has at least one endpoint in $S$.

The set $S$ is a vertex cover.

Vertex Cover is in NP because a certificate is simply a proposed set $S$. We can verify in polynomial time that $|S|\leq k$ and that every edge is covered.

Footnotes

1. NP Completeness lecture notes - Definition of Vertex Cover, its membership in NP, and the 3-SAT reduction. ↩ ↩²

Construction of the graph

Given a 3-SAT formula $\varphi$ with $n$ variables and $m$ clauses, construct a graph $G_\varphi$ as follows.

1. Variable gadgets

For every variable $x_i$, create two vertices:

• one vertex labeled $x_i$;
• one vertex labeled $\neg x_i$.

Connect these two vertices by an edge.

Thus, every variable creates a pair:

$$(x_i,\neg x_i).$$

Because the pair is connected by an edge, every vertex cover must select at least one of them. Selecting $x_i$ represents setting $x_i=\mathrm{true}$, while selecting $\neg x_i$ represents setting $x_i=\mathrm{false}$.

There are $n$ variable edges, so any vertex cover must contain at least $n$ vertices from the variable gadgets.

2. Clause gadgets

For every clause

$$C_j=(\ell_{j1}\lor \ell_{j2}\lor \ell_{j3}),$$

create three new vertices:

$$c_{j1},c_{j2},c_{j3}.$$

Connect all three clause vertices to one another, forming a triangle:

$$(c_{j1},c_{j2}),\quad (c_{j2},c_{j3}),\quad (c_{j1},c_{j3}).$$

Each clause vertex corresponds to one literal in the clause. If $c_{jr}$ corresponds to literal $\ell_{jr}$, add an edge between $c_{jr}$ and the variable-literal vertex labeled $\ell_{jr}$.

The triangle forces every vertex cover to select at least two of its three vertices. Therefore, the $m$ clause gadgets require at least $2m$ selected vertices.

3. Set the cover bound

Define

$$k=n+2m.$$

The complete reduction is therefore

$$\varphi \longmapsto (G_\varphi,n+2m).$$

The graph contains:

• $2n+3m$ vertices;
• $n+3m+3m= n+6m$ edges if every clause contains three literal-connection edges.

The graph and the parameter $k$ are computable in time polynomial in the size of $\varphi$.

Footnotes

1. Sample Proof of NP-Completeness - Construction of variable and clause gadgets for reducing 3-SAT to Vertex Cover. ↩

Correctness Proof

We prove the central equivalence:

$$\varphi \text{ is satisfiable} \iff G_\varphi \text{ has a vertex cover of size at most } n+2m.$$

Forward direction

Assume that $\varphi$ is satisfiable. Let $\alpha$ be a satisfying assignment.

Variable gadgets

For every variable $x_i$, select exactly one of the two vertices $x_i$ and $\neg x_i$:

• select $x_i$ if $\alpha(x_i)=\mathrm{true}$;
• select $\neg x_i$ if $\alpha(x_i)=\mathrm{false}$.

This selects exactly $n$ vertices and covers every variable edge.

Clause gadgets

Because $\alpha$ satisfies every clause, each clause has at least one true literal. For a clause triangle, leave unselected a clause vertex corresponding to a true literal. Select the other two clause vertices.

This selects exactly two vertices per clause triangle, for a total of $2m$ clause vertices.

The unselected clause vertex is connected to a variable-literal vertex representing a true literal. That variable-literal vertex was selected in the variable gadget, so the connecting edge is covered.

All other edges incident to selected clause vertices are automatically covered. Therefore, the resulting set is a vertex cover of size

$$n+2m=k.$$

Hence,

$$\varphi \text{ satisfiable} \implies (G_\varphi,k) \text{ is a yes-instance of Vertex Cover}.$$

Reverse direction

Assume that $G_\varphi$ has a vertex cover $S$ with

$$|S|\leq n+2m.$$

Minimum selections forced by gadgets

Each variable pair contains an edge, so $S$ must contain at least one vertex from each pair. Therefore, $S$ contains at least $n$ variable vertices.

Each clause gadget is a triangle. A triangle has three edges, and at least two of its vertices must be selected to cover all three edges. Therefore, $S$ contains at least $2m$ clause vertices.

Thus, every vertex cover has size at least

$$n+2m.$$

Since $|S|\leq n+2m$, the cover must contain exactly:

• one vertex from every variable pair;
• two vertices from every clause triangle.

Deriving a truth assignment

Define an assignment $\alpha$ by:

• $\alpha(x_i)=\mathrm{true}$ if $x_i\in S$;
• $\alpha(x_i)=\mathrm{false}$ if $\neg x_i\in S$.

Exactly one vertex from each pair is selected, so this assignment is well-defined.

Showing every clause is satisfied

Consider a clause triangle. Exactly two of its vertices are in $S$, so exactly one clause vertex is not in $S$. Let that unselected vertex correspond to literal $\ell$.

The edge connecting this clause vertex to the variable-literal vertex for $\ell$ must be covered. Since the clause vertex is not selected, its literal vertex must be selected.

By the way the assignment was defined, selecting the vertex for $\ell$ means that $\ell$ is true. Therefore, the clause contains a true literal.

Since this holds for every clause, $\alpha$ satisfies $\varphi$.

Hence,

$$(G_\varphi,k) \text{ is a yes-instance} \implies \varphi \text{ is satisfiable}.$$

Combining both directions:

$$\varphi \in \mathrm{3SAT} \iff (G_\varphi,n+2m)\in \mathrm{VERTEX\text{-}COVER}.$$

Why the Clause Triangle Works

The clause triangle encodes the requirement that at least one literal in each clause must be true.

A triangle requires two selected vertices in every vertex cover. Consequently, exactly one clause vertex can remain unselected when the cover has the minimum allowed size.

That one unselected clause vertex identifies a literal that must be true:

1. The unselected clause vertex is connected to its corresponding literal vertex.
2. The connecting edge must still be covered.
3. Therefore, the corresponding literal vertex must be selected.
4. Selection of that literal vertex represents a satisfying truth value.

This is the central gadget invariant:

$$\text{one unselected clause vertex} \Longrightarrow \text{one true literal in the clause}.$$

The construction uses the complement relationship between Vertex Cover and Independent Set as an additional perspective. For any graph $G=(V,E)$,

$$S \text{ is an independent set} \iff V\setminus S \text{ is a vertex cover}.$$

This relationship is often useful when designing or checking graph reductions.

Footnotes

1. NP-Complete Problems lecture notes - Relationship among Independent Set, Vertex Cover, and polynomial reductions. ↩