NP Complere 2

Chapter 13
Some N P-Complete Problems
13.1 Statements of the Problems
In this chapter we will show that certain classical algo-

rithmic problems are N P-complete.
This chapter is heavily inspired by Lewis and Papadim-

itriou’s excellent treatment [?].
In order to study the complexity of these problems in

terms of resource (time or space) bounded Turing ma-
chines (or RAM programs), it is crucial to be able to
encode instances of a problem P as strings in a language
LP .
651
652 CHAPTER 13. SOME N P-COMPLETE PROBLEMS
Then an instance of a problem P is solvable iff the corre-

sponding string belongs to the language LP .
This implies that our problems must have a yes–no an-

swer, which is not always the usual formulation of opti-
mization problems where what is required is to find some
optimal solution, that is, a solution minimizing or maxi-
mizing so objective (cost) function F .
For example the standard formulation of the traveling

salesman problem asks for a tour (of the cities) of minimal
cost.
Fortunately, there is a trick to reformulate an optimiza-

tion problem as a yes–no answer problem, which is to
explicitly incorporate a budget (or cost) term B into the
problem, and instead of asking whether some objective
function F has a minimum or a maximum w, we ask
whether there is a solution w such that F (w) ≤ B in the
case of a minimum solution, or F (w) ≥ B in the case of
a maximum solution.
13.1. STATEMENTS OF THE PROBLEMS 653
We will see several examples of this technique in Problems

5–8 listed below.
The problems that will consider are

(1) Exact Cover
(2) Hamiltonian Cycle for directed graphs
(3) Hamiltonian Cycle for undirected graphs
(4) The Traveling Salesman Problem
(5) Independent Set
(6) Clique
(7) Node Cover
(8) Knapsack, also called subset sum
(9) Inequivalence of ∗-free Regular Expressions
(10) The 0-1-integer programming problem
We begin by describing each of these problems.

(1) Exact Cover
We are given a finite nonempty set U = {u1, . . . , un}

(the universe), and a family F = {S1, . . . , Sm} of
m ≥ 1 nonempty subsets of U .
The question is whether there is an exact cover , that

is, a subfamily C ⊆ F of subsets in F such that the
sets in C are disjoint and their union is equal to U .
For example, let

U = {u1, u2, u3, u4, u5, u6}, and let F be the family
F = {{u1, u3}, {u2, u3, u6}, {u1, u5}, {u2, u3, u4},
{u5, u6}, {u2, u4}}.
The subfamily
C = {{u1, u3}, {u5, u6}, {u2, u4}}
is an exact cover.
It is easy to see that Exact Cover is in N P.
To prove that it is N P-complete, we will reduce the

Satisfiability Problem to it.
This means that we provide a method running in poly-

nomial time that converts every instance of the Satis-
fiability Problem to an instance of Exact Cover,
such that the first problem has a solution iff the con-
verted problem has a solution.
(2) Hamiltonian Cycle (for Directed Graphs)
Recall that a directed graph G is a pair G = (V, E),

where E ⊆ V × V .
Elements of V are called nodes (or vertices). A pair

(u, v) ∈ E is called an edge of G.
We will restrict ourselves to simple graphs, that is,

graphs without edges of the form (u, u);
equivalently, G = (V, E) is a simple graph if whenever

(u, v) ∈ E, then u ̸= v.
Given any two nodes u, v ∈ V , a path from u to v is

any sequence of n + 1 edges (n ≥ 0)
(u, v1), (v1, v2), . . . , (vn, v).
(If n = 0, a path from u to v is simply a single edge,
(u, v).)
A directed graph G is strongly connected if for every

pair (u, v) ∈ V × V , there is a path from u to v. A
closed path, or cycle, is a path from some node u to
itself.
We will restrict out attention to finite graphs, i.e.

graphs (V, E) where V is a finite set.
Definition 13.1. Given a directed graph G, a Hamil-

tonian cycle is a cycle that passes through all the
nodes exactly once (note, some edges may not be tra-
versed at all).
Hamiltonian Cycle Problem (for Directed

Graphs): Given a directed graph G, is there an
Hamiltonian cycle in G?
Is there is a Hamiltonian cycle in the directed graph

D shown in Figure 13.1?
Figure 13.1: A tour “around the world.”

Finding a Hamiltonian cycle in this graph does not

appear to be so easy! A solution is shown in Figure
13.2 below.
v20
v1
v8 v2
v19 v16
v9 v15
v7 v3
v4
v6 v5
v10 v14
v11 v12 v13
v17
v18
Figure 13.2: A Hamiltonian cycle in D.
It is easy to see that Hamiltonian Cycle (for Di-

rected Graphs) is in N P.
To prove that it is N P-complete, we will reduce Ex-

act Cover to it.

nomial time that converts every instance of Exact
Cover to an instance of Hamiltonian Cycle (for
Directed Graphs) such that the first problem has
a solution iff the converted problem has a solution.
This is perphaps the hardest reduction.
(3) Hamiltonian Cycle (for Undirected Graphs)
Recall that an undirected graph G is a pair G =

(V, E), where E is a set of subsets {u, v} of V con-
sisting of exactly two distinct elements.
Elements of V are called nodes (or vertices). A pair

{u, v} ∈ E is called an edge of G.
Given any two nodes u, v ∈ V , a path from u to v is

any sequence of n nodes (n ≥ 2)
u = u1, u2, . . . , un = v
such that {ui, ui+1} ∈ E for i = 1, . . . , n − 1. (If

n = 2, a path from u to v is simply a single edge,
{u, v}.)
An undirected graph G is connected if for every pair

(u, v) ∈ V × V , there is a path from u to v.
A closed path, or cycle, is a path from some node u

to itself.
Definition 13.2. Given an undirected graph G, a

Hamiltonian cycle is a cycle that passes through all
the nodes exactly once (note, some edges may not be
traversed at all).
Hamiltonian Cycle Problem (for Undirected

Graphs): Given an undirected graph G, is there an
Hamiltonian cycle in G?
An instance of this problem is obtained by changing

every directed edge in the directed graph of Figure
13.1 to an undirected edge.
The directed Hamiltonian cycle given in Figure 13.2

is also an undirected Hamiltonian cycle of the undi-
rected graph of Figure 13.3.
Figure 13.3: A tour “around the world,” undirected version.
We see immediately that Hamiltonian Cycle (for

Undirected Graphs) is in N P.
To prove that it is N P-complete, we will reduce Hamil-

tonian Cycle (for Directed Graphs) to it.

nomial time that converts every instance of Hamil-
tonian Cycle (for Directed Graphs) to an in-
stance of Hamiltonian Cycle (for Undirected
Graphs) such that the first problem has a solution
iff the converted problem has a solution. This is an
easy reduction.
(4) Traveling Salesman Problem
We are given a set {c1, c2, . . . , cn} of n ≥ 2 cities, and

an n × n matrix D = (dij ) of nonnegative integers,
where dij is the distance (or cost) of traveling from
city ci to city cj .
We assume that dii = 0 and dij = dji for all i, j, so

that the matrix D is symmetric and has zero diagonal.
Traveling Salesman Problem: Given some n×n

matrix D = (dij ) as above and some integer B ≥ 0
(the budget of the traveling salesman), find a permu-
tation π of {1, 2, . . . , n} such that
c(π) = dπ(1)π(2) + dπ(2)π(3) + · · ·

+ dπ(n−1)π(n) + dπ(n)π(1) ≤ B.
The quantity c(π) is the cost of the trip specified by

π.
The Traveling Salesman Problem has been stated in

terms of a budget so that it has a yes or no answer,
which allows us to convert it into a language. A mini-
mal solution corresponds to the smallest feasible value
of B.
Example 13.1. Consider the 4×4 symmetric matrix

given by ⎛ ⎞
0 2 1 1
⎜ ⎟
⎜ 2 0 1 1⎟
⎜ ⎟
D=⎜ ⎟,
⎜ 1 1 0 3⎟
⎝ ⎠
1 1 3 0
and the budget B = 4. The tour specified by the

permutation
' (
1 2 3 4
π=
1 4 2 3
has cost 4, since

c(π) = dπ(1)π(2) + dπ(2)π(3) + dπ(3)π(4) + dπ(4)π(1)
= d14 + d42 + d23 + d31
= 1 + 1 + 1 + 1 = 4.
The cities in this tour are traversed in the order
(1, 4, 2, 3, 1).
It is clear that the Traveling Salesman Problem

is in N P.
To show that it is N P-complete, we reduce the Hamil-

tonian Cycle Problem (Undirected Graphs)
to it.

nomial time that converts every instance of Hamil-
tonian Cycle Problem (Undirected Graphs)
to an instance of the Traveling Salesman Prob-
lem such that the first problem has a solution iff the
converted problem has a solution.
(5) Independent Set
The problem is this: Given an undirected graph G =

(V, E) and an integer K ≥ 2, is there a set C of nodes
with |C| ≥ K such that for all vi, vj ∈ C, there is no
edge {vi, vj } ∈ E?
A maximal independent set with 3 nodes is shown in

Figure 13.4.
Figure 13.4: A maximal Independent Set in a graph
A maximal solution corresponds to the largest feasible

value of K.
The problem Independent Set is obviously in N P.
To show that it is N P-complete, we reduce

Exact 3-Satisfiability to it.

nomial time that converts every instance of Exact 3-
Satisfiability to an instance of Independent Set
such that the first problem has a solution iff the con-
verted problem has a solution.
(6) Clique

(V, E) and an integer K ≥ 2, is there a set C of nodes
with |C| ≥ K such that for all vi, vj ∈ C, there is
some edge {vi, vj } ∈ E?
Equivalently, does G contain a complete subgraph

with at least K nodes?
A maximal clique with 4 nodes is shown in Figure

13.5.
Figure 13.5: A maximal Clique in a graph

value of K.
The problem Clique is obviously in N P.
To show that it is N P-complete, we reduce Inde-

pendent Set to it.

nomial time that converts every instance of Inde-
pendent Set to an instance of Clique such that the
first problem has a solution iff the converted problem
has a solution.
(7) Node Cover

(V, E) and an integer B ≥ 2, is there a set C of
nodes with |C| ≤ B such that C covers all edges
in G, which means that for every edge {vi, vj } ∈ E,
either vi ∈ C or vj ∈ C?
A minimal node cover with 6 nodes is shown in Figure

13.6.
A minimal solution corresponds to the smallest feasi-

ble value of B.
Figure 13.6: A minimal Node Cover in a graph
The problem Node Cover is obviously in N P.
To show that it is N P-complete, we reduce Inde-

pendent Set to it.

nomial time that converts every instance of Inde-
pendent Set to an instance of Node Cover such
that the first problem has a solution iff the converted
problem has a solution.
The Node Cover problem has the following interesting

interpretation:
think of the nodes of the graph as rooms of a mu-

seum (or art gallery etc.), and each edge as a straight
corridor that joins two rooms.
Then Node Cover may be useful in assigning as few

as possible guards to the rooms, so that all corridors
can be seen by a guard.
(8) Knapsack (also called Subset sum)
The problem is this: Given a finite nonempty set

S = {a1, a2, . . . , an} of nonnegative integers, and
some integer K ≥ 0, all represented in binary, is there
a nonempty subset I ⊆ {1, 2, . . . , n} such that
)
ai = K?
i∈I
A “concrete” realization of this problem is that of

a hiker who is trying to fill her/his backpack to its
maximum capacity with items of varying weights or
values.
It is easy to see that the Knapsack Problem is in

N P.
To show that it is N P-complete, we reduce Exact

Cover to it.

nomial time that converts every instance of Exact
Cover to an instance of Knapsack Problem such
that the first problem has a solution iff the converted
problem has a solution.
Remark: The 0 -1 Knapsack Problem is de-

fined as the following problem.
Given a set of n items, numbered from 1 to n, each

with a weight wi ∈ N and a value vi ∈ N, given a
maximum capacity W ∈ N and a budget B ∈ N, is
there a set of n variables x1, . . . , xn with xi ∈ {0, 1}
such that
n
)
xivi ≥ B,
i=1
)n
xiwi ≤ W.
i=1
Informally, the problem is to pick items to include in

the knapsack so that the sum of the values exceeds a
given minimum B (the goal is to maximize this sum),
and the sum of the weights is less than or equal to the
capacity W of the knapsack.

value of B.
The Knapsack Problem as we defined it (which is

how Lewis and Papadimitriou define it) is the special
case where vi = wi = 1 for i = 1, . . . , n and W = B.
For this reason, it is also called the Subset Sum

Problem.
Clearly, the Knapsack (Subset Sum) Problem re-

duces to the 0 -1 Knapsack Problem, and thus the
0 -1 Knapsack Problem is also NP-complete.
Recall that the problem of deciding the equivalence

R1 ∼
= R2 of two regular expressions R1 and R2 is the
problem of deciding whether R1 and R2 define the
same language, that is, L[R1] = L[R2].
Is this problem in N P?
In order to show that the equivalence problem for reg-

ular expressions is in N P we would have to be able
to somehow check in polynomial time that two ex-
pressions define the same language, but this is still an
open problem.
What might be easier is to decide whether two regular

expressions R1 and R2 are inequivalent.
For this, we just have to find a string w such that

either w ∈ L[R1] − L[R2] or w ∈ L[R2] − L[R1].
The problem is that if we can guess such a string w,

we still have to check in polynomial time that w ∈
(L[R1] − L[R2]) ∪ (L[R2] − L[R1]), and this implies
that there is a bound on the length of w which is
polynomial in the sizes of R1 and R2.
Again, this is an open problem.
To obtain a problem in N P we have to consider a

restricted type of regular expressions, and it turns out
that ∗-free regular expressions are the right candidate.
A ∗-free regular expression is a regular expression

which is built up from the atomic expressions using
only + and ·, but not ∗. For example,
R = ((a + b)aa(a + b) + aba(a + b)b)
is such an expression.
It is easy to see that if R is a ∗-free regular expression,

then for every string w ∈ L[R] we have |w| ≤ |R|. In
particular, L[R] is finite.
The above observation shows that if R1 and R2 are

∗-free and if there is a string w ∈ (L[R1] − L[R2]) ∪
(L[R2] − L[R1]), then |w| ≤ |R1| + |R2|, so we can
indeed check this in polynomial time.
It follows that the inequivalence problem for ∗ -free

regular expressions is in N P.
To show that it is N P-complete, we reduce the Sat-

isfiability Problem to it.

nomial time that converts every instance of Satisfia-
bility Problem to an instance of Inequivalence
of Regular Expressions such that the first prob-
lem has a solution iff the converted problem has a
solution.
(10) 0-1 integer programming problem
Let A be any p × q matrix with integer coefficients

and let b ∈ Zp be any vector with integer coefficients.
The 0-1 integer programming problem is to

find whether a system of p linear equations in q vari-
ables
a11x1 + · · · + a1q xq = b1
.. ..
ai1x1 + · · · + aiq xq = bi
.. ..
ap1x1 + · · · + apq xq = bp
with aij , bi ∈ Z has any solution x ∈ {0, 1}q , that is,

with xi ∈ {0, 1}.
In matrix form, if we let

⎛ ⎞ ⎛ ⎞ ⎛ ⎞
a11 · · · a1q b1 x1
⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎜ .
A=⎝ . . .
.. . ⎟ , b=⎜ .. ⎟ , x=⎜ .. ⎟ ,
⎠ ⎝ ⎠ ⎝ ⎠
ap1 · · · apq bp xq
then we write the above system as
Ax = b.
It is immediate that 0-1 integer programming

problem is in N P.
To prove that it is N P-complete we reduce the

bounded tiling problem to it.
This means that we provide a method running in

polynomial time that converts every instance of the
bounded tiling problem to an instance of the 0-
1 integer programming problem such that the
first problem has a solution iff the converted problem
has a solution.
13.2. PROOFS OF N P-COMPLETENESS 681
13.2 Proofs of N P-Completeness
(1) Exact Cover
To prove that Exact Cover is N P-complete, we

reduce the Satisfiability Problem to it:
Satisfiability Problem ≤P Exact Cover
Given a set F = {C1, . . . , Cℓ} of ℓ clauses constructed

from n propositional variables x1, . . . , xn, we must
construct in polynomial time an instance τ (F ) =
(U, F) of Exact Cover such that F is satisfiable
iff τ (F ) has a solution.
Example 13.2. If
F = {C1 = (x1 ∨ x2), C2 = (x1 ∨ x2 ∨ x3), C3 = (x2),
C4 = (x2 ∨ x3)},
then the universe U is given by
U = {x1, x2, x3, C1, C2, C3, C4, p11, p12, p21, p22, p23, p31,
p41, p42},
and the family F consists of the subsets
{p11}, {p12}, {p21}, {p22}, {p23}, {p31}, {p41}, {p42}

T1,F = {x1, p11}
T1,T = {x1, p21}
T2,F = {x2, p22, p31}
T2,T = {x2, p12, p41}
T3,F = {x3, p23}
T3,T = {x3, p42}
{C1, p11}, {C1, p12}, {C2, p21}, {C2, p22}, {C2, p23},
{C3, p31}, {C4, p41}, {C4, p42}.
It is easy to check that the set C consisting of the

following subsets is an exact cover:
T1,T = {x1, p21}, T2,T = {x2, p12, p41}, T3,F = {x3, p23},
{C1, p11}, {C2, p22}, {C3, p31}, {C4, p42}.
The general method to construct (U, F) from

F = {C1, . . . , Cℓ} proceeds as follows. Say
Cj = (Lj1 ∨ · · · ∨ Ljmj )
is the jth clause in F , where Ljk denotes the kth

literal in Cj and mj ≥ 1. The universe of τ (F ) is the
set
U = {xi | 1 ≤ i ≤ n} ∪ {Cj | 1 ≤ j ≤ ℓ}
∪ {pjk | 1 ≤ j ≤ ℓ, 1 ≤ k ≤ mj }
where in the third set pjk corresponds to the kth literal

in Cj .
The following subsets are included in F:

(a) There is a set {pjk } for every pjk .
(b) For every boolean variable xi, the following two
sets are in F:
Ti,T = {xi} ∪ {pjk | Ljk = xi}
which contains xi and all negative occurrences of
xi, and
Ti,F = {xi} ∪ {pjk | Ljk = xi}
which contains xi and all its positive occurrences.
Note carefully that Ti,T involves negative occur-
rences of xi whereas Ti,F involves positive occur-
rences of xi.
(c) For every clause Cj , the mj sets {Cj , pjk } are in
F.
It remains to prove that F is satisfiable iff τ (F ) has

a solution.
We claim that if v is a truth assignement that satisfies

F , then we can make an exact cover C as follows:
For each xi, we put the subset Ti,T in C iff v(xi) = T,

else we we put the subset Ti,F in C iff v(xi) = F.
Also, for every clause Cj , we put some subset {Cj , pjk }

in C for a literal Ljk which is made true by v.
By construction of Ti,T and Ti,F, this pjk is not in

any set in C selected so far. Since by hypothesis F is
satisfiable, such a literal exists for every clause.
Having covered all xi and Cj , we put a set {pjk } in C

for every remaining pjk which has not yet been covered
by the sets already in C.
Going back to Example 13.2, the truth assigment

v(x1) = T, v(x2) = T, v(x3) = F satisfies
F = {C1 = (x1 ∨ x2), C2 = (x1 ∨ x2 ∨ x3), C3 = (x2),

C4 = (x2 ∨ x3)},
so we put
T1,T = {x1, p21}, T2,T = {x2, p12, p41}, T3,F = {x3, p23},
{C1, p11}, {C2, p22}, {C3, p31}, {C4, p42}
in C.
Conversely, if C is an exact cover of τ (F ), we define a

truth assigment as follows:
For every xi, if Ti,T is in C, then we set v(xi) = T,

else if Ti,F is in C, then we set v(xi) = F.
Example 13.3. Given the exact cover
T1,T = {x1, p21}, T2,T = {x2, p12, p41}, T3,F = {x3, p23},
{C1, p11}, {C2, p22}, {C3, p31}, {C4, p42},
we get the satisfying assigment v(x1) = T, v(x2) =

T, v(x3) = F .
If we now consider the proposition is CNF given by
F2 = {C1 = (x1 ∨ x2), C2 = (x1 ∨ x2 ∨ x3), C3 = (x2),

C4 = (x2 ∨ x3 ∨ x4)}
where we have added the boolean variable x4 to clause

C4, then U also contains x4 and p43 so we need to add
the following subsets to F:
T4,F = {x4, p43}, T4,T = {x4}, {C4, p43}, {p43}.

The truth assigment v(x1) = T, v(x2) = T, v(x3) =

F, v(x4) = T satisfies F2, so an exact cover C is
T1,T = {x1, p21}, T2,T = {x2, p12, p41},

T3,F = {x3, p23}, T4,T = {x4},
{C1, p11}, {C2, p22}, {C3, p31}, {C4, p42}, {p43}.
Observe that this time, because the truth assignment

v makes both literals corresponding to p42 and p43 true
and since we picked p42 to form the subset {C4, p42},
we need to add the singleton {p43} to C to cover all
elements of U .
(2) Hamiltonian Cycle (for Directed Graphs)
To prove that Hamiltonian Cycle (for Directed

Graphs) is N P-complete, we will reduce Exact
Cover to it:
Exact Cover ≤P Hamiltonian Cycle (for Di-

rected Graphs)
We need to find an algorithm working in polynomial

time that converts an instance (U, F) of Exact Cover
to a directed graph G = τ (U, F) such that G has a
Hamiltonian cycle iff (U, F) has an exact cover.
The construction of the graph G uses a trick involving

a small subgraph Gad with 7 (distinct) nodes known
as a gadget shown in Figure 13.7.
a b
u v w
d c
Figure 13.7: A gadget Gad
The crucial property of the graph Gad is that if Gad

is a subgraph of a bigger graph G in such a way that
no edge of G is incident to any of the nodes u, v, w
unless it is one of the eight edges of Gad incident to
the nodes u, v, w, then for any Hamiltonian cycle
in G, either the path (a, u), (u, v), (v, w), (w, b) is
traversed or the path (c, w), (w, v), (v, u), (u, d) is
traversed, but not both.
It is convenient to use the simplified notation with a

special type of edge labeled with the exclusive or sign
⊕ between the “edges” between a and b and between
d and c, as shown in Figure 13.8.
a b
d c
Figure 13.8: A shorthand notation for a gadget
This abbreviating device can be extended to the sit-

uation where we build gadgets between a given pair
(a, b) and several other pairs (c1, d1), . . . , (cm, dm), all
nodes beeing distinct, as illustrated in Figure 13.9.
Either all three edges (c1, d1), (c2, d2), (c3, d3) are tra-
versed or the edge (a, b) is traversed, and these possi-
bilities are mutually exclusive.
a b
⊕ ⊕
d1 c3
⊕
c1 d3
d2 c2
Figure 13.9: A shorthand notation for several gadgets

Example 13.4. The construction of the graph is il-

lustrated in Figure 13.10 for the instance of the exact
cover problem given by
U = {u1, u2, u3, u4}, F = {S1 = {u3, u4},
S2 = {u2, u3, u4}, S3 = {u1, u2}}.
u4 S0
u3
⊕ ⊕ S1
u2 ⊕
⊕
S2
u1 ⊕
u0 S3
Figure 13.10: The directed graph constructed from the data (U, F ) of Example 13.4
In our example, there is a Hamiltonian where the blue

edges are traversed between the Si nodes, and the red
edges are traversed between the uj nodes.
An edge between Si nodes which is not connected by

another ⊕-edge is called a short edge, and otherwise
a long edge.
The Hamiltonian is the following path:
short (S0, S1), long (S1, S2), short (S2, S3), (S3, u0),
(u0, u1)3, (u1, u2)3, (u2, u3)1, (u3, u4)1, (u4, S0).
Each edge between uj−1 and uj corresponds to an

occurrence of uj in some uniquely determined set
Si ∈ F (that is, uj ∈ Si), and we put an exclusive-
or edge between the edge (uj−1, uj ) and the the long
edge (Si−1, Si) between Si−1 and Si,
The subsets corresponding to the short (Si−1, Si) edges

are S1 and S3, and indeed C = {S1, S3} is an exact
cover.
It can be proved that (U, F) has an exact cover iff the

graph G = τ (U, F) has a Hamiltonian cycle.
For example, if C is an exact cover for (U, F), then

consider the path in G obtained by traversing each
short edge (Si−1, Si) for which Si ∈ C, each edge
(uj−1, uj ) such that uj ∈ Si, which means that this
edge is connected by a ⊕-sign to the long edge (Si−1, Si)
(by construction, for each uj there is a unique such
Si), and the edges (un, S0) and (Sm, u0), then we ob-
tain a Hamiltonian cycle.
In our example, the exact cover C = {S1, S3} yields

the Hamiltonian
short (S0, S1), long (S1, S2), short (S2, S3), (S3, u0),
(u0, u1)3, (u1, u2)3, (u2, u3)1, (u3, u4)1, (u4, S0)
that we encountered earlier.
(3) Hamiltonian Cycle (for Undirected Graphs)
To show that Hamiltonian Cycle (for Undi-

rected Graphs) is N P-complete we reduce Hamil-
tonian Cycle (for Directed Graphs) to it:
Hamiltonian Cycle (for Directed Graphs)

≤P Hamiltonian Cycle (for Undirected
Graphs)
Given any directed graph G = (V, E) we need to con-

struct in polynomial time an undirected graph τ (G) =
G′ = (V ′, E ′) such that G has a (directed) Hamilto-
nian cycle iff G′ has a (undirected) Hamiltonian cycle.
We make three distinct copies v0, v1, v2 of every node

v ∈ V which we put in V ′, and for every edge (u, v) ∈
E we create five edges as illustrated in the diagram
shown in Figure 13.11.
u v =⇒ u0 u1 u2 v0 v1 v2
Figure 13.11: Conversion of a directed graph into an undirected graph

The crucial point about the graph G′ is that although

there may be several edges adjacent to a node u0 or a
node u2, the only way to reach u1 from u0 is through
the edge {u0, u1} and the only way to reach u1 from
u2 is through the edge {u1, u2}.
This implies that any Hamiltonian cycle in G′ arriving

to a node v0 along an edge (u2, v0) must continue to
node v1 and then to v2, which means that the edge
(u, v) is traversed in G.
By considering a Hamiltonian cycle in G′ or perhaps

its reversal, it is not hard to show that a Hamiltonian
cycle in G′ determines a Hamiltonian cycle in G.
Conversely, a Hamiltonian cycle in G determines a

Hamiltonian in G′.
(4) Traveling Salesman Problem
To show that the Traveling Salesman Problem

is N P-complete, we reduce the Hamiltonian Cy-
cle Problem (Undirected Graphs) to it:
Hamiltonian Cycle Problem (Undirected

Graphs) ≤P Traveling Salesman Problem
Given an undirected graph G = (V, E), we construct

an instance τ (G) = (D, B) of the traveling salesman
problem so that G has a Hamiltonian cycle iff the
traveling salesman problem has a solution.
If we let n = |V |, we have n cities and the matrix

D = (dij ) is defined as follows:
⎧
⎪
⎨0 if i = j
dij = 1 if {vi, vj } ∈ E
⎪
⎩
2 otherwise.
We also set the budget B as B = n.

Any tour of the cities has cost equal to n plus the

number of pairs (vi, vj ) such that i ̸= j and {vi, vj }
is not an edge of G. It follows that a tour of cost n
exists iff there are no pairs (vi, vj ) of the second kind
iff the tour is a Hamiltonian cycle.
(5) Independent Set
To show that Independent Set is N P-complete,

we reduce Exact 3-Satisfiability to it:
Exact 3-Satisfiability ≤P Independent Set
Recall that in Exact 3-Satisfiability every clause

Ci has exactly three literals Li1, Li2, Li3.
Given a set F = {C1, . . . , Cm} of m ≥ 2 such clauses,

we construct in polynomial time an undirected graph
G = (V, E) such that F is satisfiable iff G has an
independent set C with at least K = m nodes.
For every i (1 ≤ i ≤ m), we have three nodes ci1, ci2, ci3

corresponding to the three literals Li1, Li2, Li3 in clause
Ci, so there are 3m nodes in V .
The “core” of G consists of m triangles, one for each

set {ci1, ci2, ci3}. We also have an edge {cik , cjℓ} iff
Lik and Ljℓ are complementary literals.
Example 13.5. Let F be the set of clauses
F = {C1 = (x1 ∨ x2 ∨ x3), C2 = (x1 ∨ x2 ∨ x3),

C3 = (x1 ∨ x2 ∨ x3), C4 = (x1 ∨ x2 ∨ x3)}.
The graph G associated with F is shown in Figure

13.12.
x1 x1 x1 x1
x2 x3 x2 x3 x2 x3 x2 x3
Figure 13.12: The graph constructed from the clauses of Example 13.5
Since any three nodes in a triangle are connected, an

independent set C can have at most one node per
triangle and thus has at most m nodes. Since the
budget is K = m, we may assume that there is an
independent with m nodes.
Define a (partial) truth assignment by

.
T if Ljk = xi and cjk ∈ C
v(xi) =
F if Ljk = xi and cjk ∈ C.
Since the non-triangle edges in G link nodes corre-

sponding to complementary literals and nodes in C
are not connected, our truth assigment does not as-
sign clashing truth values to the variables xi.
Not all variables may receive a truth value, in which

case we assign an arbitrary truth value to the unas-
signed variables. This yields a satisfying assignment
for F .
In Example 13.5, the set C = {c11, c22, c32, c41} cor-

responding to the nodes shown in red in Figure 13.12
form an independent set, and they induce the partial
truth assignment v(x1) = T, v(x2) = F.
The variable x3 can be assigned an arbitrary value,

say v(x3) = F, and v is indeed a satisfying truth
assignment for F .
Conversely, if v is a truth assignment for F , then we

obtain an independent set C of size m by picking for
each clause Ci a node cik corresponding to a literal
Lik whose value under v is T.
(6) Clique
To show that Clique is N P-complete, we reduce In-

dependent Set to it:
Independent Set ≤P Clique
The key the reduction is the notion of the complement

of an undirected graph G = (V, E).
The complement Gc = (V, E c) of the graph G =

(V, E) is the graph with the same set of nodes V as
G but there is an edge {u, v} (with u ̸= v) in E c iff
{u, v} ∈
/ E.
Then, it is not hard to check that there is a bijection

between maximum independent sets in G and maxi-
mum cliques in Gc.
The reduction consists in constructing from a graph

G its complement Gc, and then G has an independent
set iff Gc has a clique.
This construction is illustrated in Figure 13.13, where

a maximum independent set in the graph G is shown
in blue and a maximum clique in the graph Gc is
shown in red.
Figure 13.13: A graph (left) and its complement (right)

(7) Node Cover
To show that Node Cover is N P-complete, we re-

duce Independent Set to it:
Independent Set ≤P Node Cover
This time the crucial observation is that if N is an

independent set in G, then the complement
C = V − N of N in V is a node cover in G.
Thus there is an independent set of size at least K

iff there is a node cover of size at most n − K where
n = |V | is the number of nodes in V .
The reduction leaves the graph unchanged and re-

places K by n − K.
An example is shown in Figure 13.14 where an inde-

pendent set is shown in blue and a node cover is shown
in red.
Figure 13.14: An inpendent set (left) and a node cover (right)

(8) Knapsack (also called Subset sum)
To show that Knapsack is N P-complete, we reduce

Exact Cover to it:
Exact Cover ≤P Knapsack
Given an instance (U, F) of set cover with

U = {u1, . . . , un} and F = {S1, . . . , Sm}, a family
of subsets of U , we need to produce in polynomial
time an instance τ (U, F) of the knapsack problem
consisting of k nonnegative integers a1, . . . , ak and
another integer K > 0 such / that there is a subset
I ⊆ {1, . . . , k} such that i∈I ai = K iff there is an
exact cover of U using subsets in F.
The trick here is the relationship between set union

and integer addition.
Example 13.6. Consider the exact cover problem

given by U = {u1, u2, u3, u4} and
F = {S1 = {u3, u4}, S2 = {u2, u3, u4}, S3 = {u1, u2}}.
We can represent each subset Sj by a binary string

aj of length 4, where the ith bit from the left is 1 iff
ui ∈ Sj , and 0 otherwise.
In our example
a1 = 0011
a2 = 0111
a3 = 1100.
Then, the trick is that some family C of subsets Sj is

an exact cover if the sum of the corresponding num-
bers aj adds up to 1111 = 24 − 1 = K.
For example,
C = {S1 = {u3, u4}, S3 = {u1, u2}}
is an exact cover and
a1 + a3 = 0011 + 1100 = 1111.
Unfortunately, there is a problem with this encoding

which has to do with the fact that addition may in-
volve carry. For example, assuming four subsets and
the universe U = {u1, . . . , u6},
11 + 13 + 15 + 24 = 63,
in binary
001011 + 001101 + 001111 + 011000 = 111111,
but if we convert these binary strings to the corre-
sponding subsets we get the subsets
S1 = {u3, u5, u6}
S2 = {u3, u4, u6}
S3 = {u3, u4, u5, u6}
S4 = {u2, u3},
which are not disjoint and do not cover U .
The fix is surprisingly simple: use base m (where m

is the number of subsets in F) instead of base 2.
Example 13.7. Consider the exact cover problem
given by U = {u1, u2, u3, u4, u5, u6} and F given by
S1 = {u3, u5, u6}

S2 = {u3, u4, u6}
S3 = {u3, u4, u5, u6}
S4 = {u2, u3},
S5 = {u1, u2, u4}.
In base m = 5, the numbers corresponding to S1, . . . , S5

are
a1 = 001011
a2 = 001101
a3 = 001111
a4 = 011000
a5 = 110100.
This time,
a1 + a2 + a3 + a4 = 001011 + 001101 + 001111
+ 011000
= 014223 ̸= 111111,
so {S1, S2, S3, S4} is not a solution. However
a1 + a5 = 001011 + 110100 = 111111,
and C = {S1, S5} is an exact cover.
Thus, given an instance (U, F) of Exact Cover

where U = {u1, . . . , un} and F = {S1, . . . , Sm} the
reduction to Knapsack consists in forming the m
numbers a1, . . . , am (each of n bits) encoding the sub-
sets Sj , namely aji = 1 iff ui ∈ Sj , else 0, and to let
K = 1 + m2 + · · · + mn−1, which is represented in
base m by the string 011 ·12· · 113.
n
/
In testing whether i∈I ai = K for some subset I ⊆
{1, . . . , m}, we use arithmetic in base m.
If a candidate solution C involves at most m − 1 sub-

sets, then since the corresponding numbers are added
in base m, a carry can never happen.
If the candidate solution involves all m subsets, then

a1 + · · · + am = K iff F is a partition of U , since
otherwise some bit in the result of adding up these m
numbers in base m is not equal to 1, even if a carry
occurs.
To show that Inequivalence of ∗-free Regular

Expressions is N P-complete, we reduce the Sat-
isfiability Problem to it:
Satisfiability Problem ≤P Inequivalence of ∗-

free Regular Expressions
We already argued that Inequivalence of ∗-free

Regular Expressions is in N P because if R is a ∗-
free regular expression, then for every string w ∈ L[R]
we have |w| ≤ |R|.
We reduce the Satisfiability Problem to the In-

equivalence of ∗-free Regular Expressions as
follows.
For any set of clauses P = C1 ∧ · · · ∧ Cp, if the

propositional variables occurring in P are x1, . . . , xn,
we produce two ∗-free regular expressions R, S over
Σ = {0, 1}, such that P is satisfiable iff LR ̸= LS .
The expression S is actually
S = (0 + 1)(0 + 1) · · · (0 + 1) .
0 12 3
n
The expression R is of the form
R = R1 + · · · + Rp,
where Ri is constructed from the clause Ci in such a

way that LRi corresponds precisely to the set of truth
assignments that falsify Ci; see below.
Given any clause Ci, let Ri be the ∗-free regular ex-

pression defined such that, if xj and xj both belong
to Ci (for some j), then Ri = ∅, else
Ri = Ri1 · Ri2 · · · Rin ,
where Rij is defined by
⎧
⎨0 if xj is a literal of Ci
Rij = 1 if xj is a literal of Ci
⎩
(0 + 1) if xj does not occur in Ci.
(10) 0-1 integer programming problem
It is easy to check that the problem is in N P.
To prove that the is N P-complete we reduce the

bounded-tiling problem to it:
bounded-tiling problem ≤P 0-1 integer pro-

gramming problem
Given a tiling problem, ((T , V, H), s4, σ0), we create a

0-1-valued variable xmnt, such that xmnt = 1 iff tile t
occurs in position (m, n) in some tiling.
Write equations or inequalities expressing that a tiling

exists and then use “slack variables” to convert in-
equalities to equations.
For example, to express the fact that every position

is tiled by a single tile, use the equation
)
xmnt = 1,
t∈T
for all m, n with 1 ≤ m ≤ 2s and 1 ≤ n ≤ s. We

leave the rest as as exercise.
13.3. SUCCINCT CERTIFICATES, coN P, AND EX P 717
13.3 Succinct Certificates, coN P, and EX P
All the problems considered in Section 13.1 share a com-

mon feature, which is that for each problem, a solution
is produced nondeterministically (an exact cover, a di-
rected Hamiltonian cycle, a tour of cities, an independent
set, a node cover, a clique etc.), and then this candidate
solution is checked deterministically and in polyno-
mial time. The candidate solution is a string called a
certificate (or witness).
It turns out that membership on N P can be defined in

terms of certificates.
To be a certificate, a string must satisfy two conditions:

1. It must be polynomially succinct, which means that
its length is at most a polynomial in the length of the
input.
2. It must be checkable in polynomial time.
All “yes” inputs to a problem in N P must have at least

one certificate, while all “no” inputs must have none.
The notion of certificate can be formalized using the no-

tion of a polynomially balanced language.
Definition 13.3. Let Σ be an alphabet, and let “;” be

a symbol not in Σ. A language L′ ⊆ Σ∗; Σ∗ is said to be
polynomially balanced if there exists a polynomial p(X)
such that for all x, y ∈ Σ∗, if x; y ∈ L′ then |y| ≤ p(|x|).
Suppose L′ is a polynomially balanced language and that

L′ ∈ P. Then we can consider the language
L = {x ∈ Σ∗ | (∃y ∈ Σ∗)(x; y ∈ L′)}.
The intuition is that for each x ∈ L, the set
{y ∈ Σ∗ | x; y ∈ L′}
is the set of certificates of x.

For every x ∈ L, a Turing machine can nondetermin-

istically guess one of its certificates y, and then use the
deterministic Turing machine for L′ to check in polyno-
mial time that x; y ∈ L′. It follows that L ∈ N P.
Conversely, if L ∈ N P and the alphabet Σ has at least

two symbols, we can encode the paths in the computation
tree for every input x ∈ L, and we obtain a polynomially
balanced language L′ ⊆ Σ∗; Σ∗ in P such that
L = {x ∈ Σ∗ | (∃y ∈ Σ∗)(x; y ∈ L′)}.
In summary, we obtain the following theorem.
Theorem 13.1. Let L ⊆ Σ∗ be a language over an

alphabet Σ with at least two symbols, and let “;” be a
symbol not in Σ. Then L ∈ N P iff there is a polyno-
mially balanced language L′ ⊆ Σ∗; Σ∗ such that L′ ∈ P
and
L = {x ∈ Σ∗ | (∃y ∈ Σ∗)(x; y ∈ L′)}.

A striking illustration of the notion of succint certificate

is illustrated by the set of composite integers, namely
those natural numbers n ∈ N that can be written as the
product pq of two numbers p, q ≥ 2 with p, q ∈ N.
For example, the number
4, 294, 967, 297
is a composite!
This is far from obvious, but if an oracle gives us the

certificate {6, 700, 417, 641}, it is easy to carry out in
polynomial time the multiplication of these two numbers
and check that it is equal to 4, 294, 967, 297.
Finding a certificate is usually (very) hard, but checking

that it works is easy. This is the point of certificates.
We conclude this section with a brief discussion of the

complexity classes coN P and EX P.
By definition,
coN P = {L | L ∈ N P},
that is, coN P consists of all complements of languages

in N P.
Since P ⊆ N P and P is closed under complementation,
P ⊆ coN P,
but nobody knows whether N P is closed under comple-

mentation, that is, nobody knows whether N P = coN P.
What can be shown is that if N P =

̸ coN P then
P=
̸ N P.
However it is possible that P = ̸ N P and yet N P =

coN P, although this is considered unlikely.
Of course, P ⊆ N P ∩ coN P.
There are problems in N P ∩ coN P not known to be in

P. One of the most famous in the following problem:
Integer factorization problem:
Given an integer N ≥ 3, and another integer M (a bud-

get) such that 1 < M < N , does N have a factor d with
1 < d ≤ M?
That Integer factorization is in N P is clear.

To show that Integer factorization is in coN P, we

can guess a factorization of N into distinct factors all
greater than M , check that they are prime using the re-
sults of Chapter ?? showing that testing primality is in
N P (even in P, but that’s much harder to prove), and
then check that the product of these factors is N .
It is widely believed that Integer factorization does

not belong to P, which is the technical justification for
saying that this problem is hard.
Most cryptographic algorithms rely on this unproven fact.
If Integer factorization was either N P-complete or

coN P-complete, then we would have N P = coN P,
which is considered very unlikely.
√
Remark: If N ≤ M < N , the above problem is
equivalent to asking whether N is prime.
A natural instance of a problem in coN P is the unsatis-

fiability problem for propositions, namely deciding that
a proposition P has no satisfying assignmnent.
A proposition P (in CNF) is falsifiable if there is some

truth assigment v such that 4
v (P ) = F.
It is obvious that the set of falsifiable propositions is in

N P. Since a proposition P is valid iff P is not falsifiable,
the validity (or tautology) problem TAUT for proposi-
tions is in coN P.
In fact, TAUT is coN P-complete.
Despite the fact that this problem has been extensively

studied, not much is known about its exact complexity.
The reasoning used to show that TAUT is coN P-complete

can also be used to show the following interesting result.
Proposition 13.2. If a language L is N P-complete,

then its complement L is coN P-complete.
The class EX P is defined as follows.
Definition 13.4. A deterministic Turing machine M is

said to be exponentially bounded if there is a polynomial
p(X) such that for every input x ∈ Σ∗, there is no ID
IDn such that
ID0 ⊢ ID1 ⊢∗ IDn−1 ⊢ IDn, with n > 2p(|x|).
The class EX P is the class of all languages that are ac-

cepted by some exponentially bounded deterministic Tur-
ing machine.
Remark: We can also define the class N EX P as in Def-

inition 13.4, except that we allow nondeterministic Turing
machines.
One of the interesting features of EX P is that it contains

N P.
Theorem 13.3. We have the inclusion N P ⊆ EX P.
It is also immediate to see that EX P is closed under

complementation. Furthermore the strict inclusion P ⊂
EX P holds.
Theorem 13.4. We have the strict inclusion

P ⊂ EX P.
The proof involves a diagonalization argument to produce

a language E such that E ∈ / P, yet E ∈ EX P.
In summary, we have the chain of inclusions
P ⊆ N P ⊆ EX P,
where the left inclusion and the right inclusion are both
open problems, but we know that at least one of these
two inclusions is strict.
We also have the inclusions
P ⊆ N P ⊆ EX P ⊆ N EX P.
Nobody knows whether EX P = N EX P, but it can be

shown that if EX P ̸= N EX P, then P ̸= N P; see
Papadimitriou [?].

NP Complere 2

Uploaded by

Copyright:

Available Formats

NP Complere 2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

NP Complere 2

Uploaded by

Copyright:

Available Formats

Chapter 13

Some N P-Complete Problems

13.1 Statements of the Problems

In this chapter we will show that certain classical algo-

This chapter is heavily inspired by Lewis and Papadim-

In order to study the complexity of these problems in

Then an instance of a problem P is solvable iﬀ the corre-

This implies that our problems must have a yes–no an-

For example the standard formulation of the traveling

Fortunately, there is a trick to reformulate an optimiza-

We will see several examples of this technique in Problems

The problems that will consider are

We begin by describing each of these problems.

(1) Exact Cover

We are given a finite nonempty set U = {u1, . . . , un}

The question is whether there is an exact cover , that

For example, let

It is easy to see that Exact Cover is in N P.

To prove that it is N P-complete, we will reduce the

This means that we provide a method running in poly-

Recall that a directed graph G is a pair G = (V, E),

Elements of V are called nodes (or vertices). A pair

We will restrict ourselves to simple graphs, that is,

equivalently, G = (V, E) is a simple graph if whenever

Given any two nodes u, v ∈ V , a path from u to v is

A directed graph G is strongly connected if for every

We will restrict out attention to finite graphs, i.e.

Definition 13.1. Given a directed graph G, a Hamil-

Hamiltonian Cycle Problem (for Directed

Is there is a Hamiltonian cycle in the directed graph

Figure 13.1: A tour “around the world.”

Finding a Hamiltonian cycle in this graph does not

v11 v12 v13

Figure 13.2: A Hamiltonian cycle in D.

It is easy to see that Hamiltonian Cycle (for Di-

To prove that it is N P-complete, we will reduce Ex-

This means that we provide a method running in poly-

Recall that an undirected graph G is a pair G =

Elements of V are called nodes (or vertices). A pair

Given any two nodes u, v ∈ V , a path from u to v is

such that {ui, ui+1} ∈ E for i = 1, . . . , n − 1. (If

An undirected graph G is connected if for every pair

A closed path, or cycle, is a path from some node u

Definition 13.2. Given an undirected graph G, a

Hamiltonian Cycle Problem (for Undirected

An instance of this problem is obtained by changing

The directed Hamiltonian cycle given in Figure 13.2

Figure 13.3: A tour “around the world,” undirected version.

We see immediately that Hamiltonian Cycle (for

To prove that it is N P-complete, we will reduce Hamil-

This means that we provide a method running in poly-

We are given a set {c1, c2, . . . , cn} of n ≥ 2 cities, and

We assume that dii = 0 and dij = dji for all i, j, so

Traveling Salesman Problem: Given some n×n

c(π) = dπ(1)π(2) + dπ(2)π(3) + · · ·

The quantity c(π) is the cost of the trip specified by

The Traveling Salesman Problem has been stated in

Example 13.1. Consider the 4×4 symmetric matrix

and the budget B = 4. The tour specified by the