Chapter 8

NP and Computational
Intractability

Slides by Kevin Wayne.

Copyright © 2005 Pearson-Addison Wesley.
All rights reserved.

1
 Algorithm Design Patterns and Anti-Patterns

Algorithm design patterns. Ex.

Greed. O(n log n) interval scheduling.
Divide-and-conquer. O(n log n) FFT.
Dynamic programming. O(n2) edit distance.
Reductions.

Algorithm design anti-patterns.

NP-completeness. O(nk) algorithm unlikely.
PSPACE-completeness. O(nk) certification algorithm unlikely.
Undecidability. No algorithm possible.

2
8.1 Polynomial-Time Reductions
 Classify Problems According to Computational Requirements

Q. Which problems will we be able to solve in practice?

A working definition. [Cobham 1964, Edmonds 1965, Rabin 1966]

Those with polynomial-time algorithms.

Yes Probably no
Shortest path Longest path
Matching 3D-matching
Min cut Max cut
2-SAT 3-SAT
Planar 4-color Planar 3-color
Bipartite vertex cover Vertex cover

Primality testing Factoring

4
 Classify Problems

Desiderata. Classify problems according to those that can be solved in

polynomial-time and those that cannot.

Huge number of fundamental problems have defied classification for

decades.

This chapter. Show that these fundamental problems are

"computationally equivalent" .

5
 Polynomial-Time Reduction

Desiderata'. Suppose we could solve X in polynomial-time. What else

could we solve in polynomial time?

Reduction. Problem X polynomial reduces to problem Y if arbitrary

instances of problem X can be solved using:
Polynomial number of standard computational steps, plus
Polynomial number of calls to oracle that solves problem Y.

Notation. X  P Y.

Remarks.
We pay for time to write down instances sent to black box 
instances of Y must be of polynomial size.
Note: Cook reducibility.

6
 Polynomial-Time Reduction

Purpose. Classify problems according to relative difficulty.

Design algorithms. If X  P Y and Y can be solved in polynomial-time,

then X can also be solved in polynomial time.

Establish intractability. If X  P Y and X cannot be solved in

polynomial-time, then Y cannot be solved in polynomial time.

Establish equivalence. If X  P Y and Y  P X, we use notation X  P Y.

7
Reduction By Simple Equivalence

Basic reduction strategies.

▪ Reduction by simple equivalence.
▪ Reduction from special case to general case.
▪ Reduction by encoding with gadgets.
 Independent Set

INDEPENDENT SET: Given a graph G = (V, E) and an integer k, is there a

subset of vertices S  V such that |S|  k, and for each edge at most
one of its endpoints is in S?

Ex. Is there an independent set of size  6? Yes.

Ex. Is there an independent set of size  7? No.

independent set

9
 Vertex Cover

VERTEX COVER: Given a graph G = (V, E) and an integer k, is there a

subset of vertices S  V such that |S|  k, and for each edge, at least
one of its endpoints is in S?

Ex. Is there a vertex cover of size  4? Yes.

Ex. Is there a vertex cover of size  3? No.

vertex cover

10
 Vertex Cover and Independent Set

Claim. VERTEX-COVER P INDEPENDENT-SET.

Pf. We show S is an independent set iff V − S is a vertex cover.

independent set

vertex cover

11
 Vertex Cover and Independent Set

Claim. VERTEX-COVER P INDEPENDENT-SET.

Pf. We show S is an independent set iff V − S is a vertex cover.


Let S be any independent set.
Consider an arbitrary edge (u, v).
S independent  u  S or v  S  u  V − S or v  V − S.
Thus, V − S covers (u, v).


Let V − S be any vertex cover.
Consider two nodes u  S and v  S.
Observe that (u, v)  E since V − S is a vertex cover.
Thus, no two nodes in S are joined by an edge  S independent set.

12
Reduction from Special Case to General Case

Basic reduction strategies.

▪ Reduction by simple equivalence.
▪ Reduction from special case to general case.
▪ Reduction by encoding with gadgets.
 Set Cover

SET COVER: Given a set U of elements, a collection S1, S2, . . . , Sm of

subsets of U, and an integer k, does there exist a collection of  k of
these sets whose union is equal to U?

Ex:

U = { 1, 2, 3, 4, 5, 6, 7 }
k=2
S1 = {3, 7} S4 = {2, 4}
S2 = {3, 4, 5, 6} S5 = {5}
S3 = {1} S6 = {1, 2, 6, 7}

14
 Vertex Cover Reduces to Set Cover

Claim. VERTEX-COVER  P SET-COVER.

Pf. Given a VERTEX-COVER instance G = (V, E), k, we construct a set
cover instance whose size equals the size of the vertex cover instance.

Construction.
Create SET-COVER instance:
– k = k, U = E, Sv = {e  E : e incident to v }
Set-cover of size  k iff vertex cover of size  k.

VERTEX COVER SET COVER

a b

e7 U = { 1, 2, 3, 4, 5, 6, 7 }
e2 e3 e4
k=2
Sa = {3, 7} Sb = {2, 4}
f e6 c Sc = {3, 4, 5, 6} Sd = {5}
e1 e5 Se = {1} Sf= {1, 2, 6, 7}
k=2
e d

15
 8.2 Reductions via "Gadgets"

Basic reduction strategies.

▪ Reduction by simple equivalence.
▪ Reduction from special case to general case.
▪ Reduction via "gadgets."
 Satisfiability

Literal: A Boolean variable or its negation. xi or xi

Clause: A disjunction of literals. C j = x1  x2  x3


Conjunctive normal form: A propositional  = C1  C2  C3  C4
formula  that is the conjunction of clauses.



SAT: Given CNF formula , does it have a satisfying truth assignment?

3-SAT: SAT where each clause contains exactly 3 literals.

Ex: ( x1  x2  x3 )  ( x1  x2  x3 )  ( x2  x3 )  ( x1  x2  x3 )
Yes: x1 = true, x2 = true x3 = false.

 17
 3 Satisfiability Reduces to Independent Set

Claim. 3-SAT  P INDEPENDENT-SET.

Pf. Given an instance  of 3-SAT, we construct an instance (G, k) of
INDEPENDENT-SET that has an independent set of size k iff  is
satisfiable.

Construction.
G contains 3 vertices for each clause, one for each literal.
Connect 3 literals in a clause in a triangle.
Connect literal to each of its negations.

x1 x2 x1

  
x2 x3 x1 x3 x2 x4

k=3  = ( x1  x2  x3 )  ( x1  x2  x3 )  ( x1  x2  x4 )
18
 3 Satisfiability Reduces to Independent Set

Claim. G contains independent set of size k = || iff  is satisfiable.

Pf.  Let S be independent set of size k.

S must contain exactly one vertex in each triangle.
Set these literals to true.
Truth assignment is consistent and all clauses are satisfied.

Pf  Given satisfying assignment, select one true literal from each

triangle. This is an independent set of size k.

x1 x2 x1

  
x2 x3 x1 x3 x2 x4

k=3  = ( x1  x2  x3 )  ( x1  x2  x3 )  ( x1  x2  x4 )
19
 Review

Basic reduction strategies.

Simple equivalence: INDEPENDENT-SET  P VERTEX-COVER.
Special case to general case: VERTEX-COVER  P SET-COVER.
Encoding with gadgets: 3-SAT  P INDEPENDENT-SET.

Transitivity. If X  P Y and Y  P Z, then X  P Z.

Pf idea. Compose the two algorithms.

Ex: 3-SAT  P INDEPENDENT-SET  P VERTEX-COVER  P SET-COVER.

20
 Self-Reducibility

Decision problem. Does there exist a vertex cover of size  k?

Search problem. Find vertex cover of minimum cardinality.

Self-reducibility. Search problem  P decision version.

Applies to all (NP-complete) problems in this chapter.
Justifies our focus on decision problems.

Ex: to find min cardinality vertex cover.

(Binary) search for cardinality k* of min vertex cover.
Find a vertex v such that G − { v } has a vertex cover of size  k* - 1.
– any vertex in any min vertex cover will have this property
Include v in the vertex cover.
Recursively find a min vertex cover in G − { v }.

21