Algorithms: Sequential, Parallel and Distributed 1-1
Chapter 26
NP-Complete Problems
At a Glance
Table of Contents
• Overview
• Objectives
• Instructor Notes
• Solutions to Selected Exercises
Algorithms: Sequential, Parallel and Distributed 1-2
Lecture Notes
Overview
In Chapter 26 we give a brief introduction to NP-complete problems. We begin the chapter by
discussing the complexities classes P and NP. This is followed by a discussion of reducibility
of problems and the complexity class NP-complete. We define the CNF SAT problem and
state Cook’s famous theorem. We then discuss reductions to establish that a number of
classical problems are NP-complete including 3-CNF SAT, Clique, Vertex Cover, Independent
Set, Three-Dimensional Matching, 3-Exact Cover, Sum of Subsets and Graph Coloring. This is
followed by a brief discussion of the class Co-NP. We finish the chapter with a discussion of
the parallel complexity classes NC and P-complete.
Chapter Objectives
After completing the chapter the student will know:
• The concept of the classes P and NP.
• The concept of NP-completeness
• The concept of a reduction from one problem to another
Instructor Notes
In this chapter we give informal definitions of the classes NP and P-complete. Of course, a
Algorithms: Sequential, Parallel and Distributed 1-3
Solutions to Selected Exercises
26.1 The decision problem is to determine whether there exists a knapsack of value at least k.
Clearly the optimization problem of computing a assignment of objects to the knapsack (not
exceeding its capacity) that maximizes the value of the knapsack, immediately yields a
26.2 We take the certificate to be the recursive tree associated with the test that n is prime if
an – 1 ≡ 1 (mod n) and a (n – 1)/p is not congruent to 1 (mod n) for any prime divisors p of n – 1,
26.3 An analogous argument to that given in Exercise 26.1 shows that the TSP for integer
26.4 By definition if A
B, then
1) There exists a mapping f that can be computed in polynomial time such that for
input I of problem A, outputs the input f(I) to problem B.
2) The answer to given input I to problem A is yes iff the answer to the input f(I) to
problem B is yes.
Given any three decision problems A,B, and C such that A
B and B
C, then there exist
26.5 Since A
B then we can always output the correct answer for input I to A simply by
26.6 Clearly, every pair of vertices in U is joined with an edge in G if and only if no pair of
vertices in U is joined with an edge in
_
G
. Thus, U is a clique in G if and only U is an
_
We now show that statements 2 and 3 are equivalent. Clearly, no two vertices of U are joined
with an edge if and only if every edge is incident to at least one node in V – U. Thus, U is an
independent set if and only V – U is a vertex cover.
27.7 In each case we define a certificate and a “yes” certificate. In each case it is clear that the
verification that the certificate is a “yes” certificate can be performed in polynomial time.
(i) 3-CNF SAT. Choose certificate to be a truth assignment. A “yes” certificate is one
that results in all clause having the value true.
(ii) Clique. Choose certificate to be a subset U of the vertices of size k. A “yes”
certificate is one such that every pair of vertices in U is joined with an edge.
26.8 Suppose A is in NP, B is NP-complete and B
A. Let C be any other problem in NP.
26.9 Note that a clause
yx
where x an y are positive or negative literals, i.e., literals x, y
{x1, …, xn}
is true iff both implications
yx
and
xy
are true. Now construct
a digraph D = (V, E), where V = {x1, …, xn}
, such that, for each clause
yx
(i.e., for the pair of implications
yx
and
xy
), we include the two directed edges
),( yx
and
),( xy
. It is easily verified that if there is a satisfying truth assignment then, for each
26.10 a) a clause of size 1 is converted into the disjunction of 4 clauses of size 3, yielding an
26.13 To determine if a graph G is bipartite we can use the following algorithm based on a
BFS: 1) Choose a node A at random
3) For every neighbor N of A
4) If no more unvisited nodes then return “BIPARITE”
26.14
(
) Given that G is n+1 colorable we can obtain a satisfying truth assignment by the
following:
1) Assign all variables that are colored with color 1 to true.
2) Assign all other variables to false.
Furthermore since the graph is (n+1)-colorable this implies that every variable and its negation
must be assigned different colors. Steps 1 and 2 satisfy condition A. Every clause node is
y
i
3) For all variables
i
x
and
i
x
which are false assign them to the color of
i
y
4) By observation 1 we can always assign every clause to a color, since all the true
26.15 Given a multiset S = {s1, s2, . . . , sn} of positive integers, the PARTITION
problem asks whether S can be partitioned into two subsets having the same sum. In other
words, does there exist a subset
},…,2,1{ nI
such that
2/)( 1
==n
ii
Ii iss
. Note that
‘S
26.16 We have shown in 26.16 that SUBSET-SUM and PARTITION are easily seen to be
equivalent, and instead of showing (as in the hint) that PARTITION 0/1 KNAPSACK, it is
26.17 Analogously to problem 26.16, rather than showing (as suggest in the hint) that
SUBSET-SUM BIN-PACKING, it is actually easier to show that PARTITION BIN-
PACKING. Given an instance S = {s1,s2, . . . , sn} of PARTITION, consider the instance
}/2,…,/2,/2{‘ 21 AsAsAsS n
=
, where
=
=n
ii
sA 1
. Note that a yes instance of PARTITION
would require that 2si/A ≤ 1, i = 1, …, n (and that S is a yes instance if, and only if,
‘S
is a yes
instance). Clearly,
‘S
is a yes instance to PARTITION if, and only if,
‘S
can be fit into 2 bins.
Hence, PARTITION BIN-PACKING.
26.18 Let be any NP-complete problem and suppose that the complement
belongs
to NP. We show that this would imply that NP = co-NP. Let A be any problem in NP. Then
there is a map f: I (A) → I () mapping the inputs to A to the inputs of , where f is
kk xxxx −121
26.21 Assume that the number of processors is equal to the total number of operations and
operands over all equations in the SLC problem. Also, assume that the expression for
26.22 a. Assume that the number of processors is equal to the total number of operations and
operands over all equations in the SLC problem. Also, assume that the expression for
each equation is represented with an expression tree. In parallel for each equation
of N1.
(iii) each node N contained
and its two children R and L containing x and