NP-COMPLETENESS
Concepts
1.1

Introduction
Almost all the algorithms we have studied thus far have been polynomial-time algorithms: on
inputs of size n, their worst-case running time is O(nk) for some constant k. However, not all problems
can be solved in polynomial time. For example, there are problems, such as Turing’s famous “Halting
Problem,” that cannot be solved by any computer, no matter how much time is provided. There arealso problems that can be solved, but not in time O(nk) for any constant k. Generally, we think ofproblems that are solvable by polynomial-time algorithms as being tractable, or easy, and problems
that require superpolynomial time as being intractable, or hard.

1.2Classes of Problems According to Runtime
P (Polynomial)
The class P consists of those problems that are solvable in polynomial time. More specifically,
they are problems that can be solved in time O(nk) for some constant k, where n is the size of the input
to the problem. Most of the problems examined in previous chapters are in P.
NP (Nondeterministic Polynomial)
The class NP consists of those problems that are “verifiable” in polynomial time. What we mean
here is that if we were somehow given a “certificate” of a solution, then we could verify that thecertificate is correct in time polynomial in the size of the input to the problem.
Any problem in P is also in NP, since if a problem is in P then we can solve it in polynomial time
without even being given a certificate. We can believe that P ⊆ NP.
NPC (NP-Complete)
A problem B is NP-complete if:
1) B ϵ NP
2) A ≤p B for all A ϵ NP
If B satisfies only property 2, we say that B is NP-hard.
No polynomial time algorithm has been discovered for an NP-Complete problem.
Again, no one has ever proven that no polynomial time algorithm can exist for any NP-Complete
problem.
A problem p ϵ NP, and any other problem p' can be translated as p in poly time. So, if p can besolved in poly time, then all problems in NP can be solved in poly time.

1.3

Optimization Problems and Decision Problems
Many problems of interest are optimization problems, in which each feasible (i.e., “legal”)
solution has an associated value, and we wish to find a feasible solution with the best value. For
example, in a problem that we call SHORTEST-PATH, we are given an undirected graph G andvertices u and v, and we wish to find a path from u to v that uses the fewest edges.
NP-completeness applies directly not to optimization problems, however, but to decision
problems, in which the answer is simply “yes” or “no” (or, more formally, “1” or “0”). We usually cancast a given optimization problem as a related decision problem by imposing a bound on the value tobe optimized. For SHORTEST-PATH, for example, a related decision problem, which we call PATH,
is whether, given a directed graph G, vertices u and v, and an integer k, a path exists from u to v
consisting of at most k edges.

1

1.4

Reductions
Given two problems A, B, we say that A is reducible to B (A ≤p B) if:
1. There exists a function f that converts the inputs of A to inputs of B in polynomial time.
time
2. A(i) = YES ↔ B(f(i)))) = YES.
YES [i.e., for an input i,, A will be satisfied if and only if B(f(i))
B(satisfies.]

1.5

Polynomial Reduction Algorithm
To solve a decision problem A in polynomial time,time
1. Use a polynomial time reduction algorithm to transform A into B
2. Run a known polynomial time algorithm for B
3. Use the answer for B as the answer for A

1.6

Proving a Language to be NP-CompleteNP
1. Prove L ∈ NP.
2. Select a known NP-complete
complete language L'.
L
3. Describe an algorithm that computes a function f mapping every instance x ∈ {0, 1}* of L' to an
instance f(x) of L.
4. Prove that the function f satisfies x ∈ L' if and only if f(x) ∈ L for all x ∈ {0, 1}*.
5. Prove that the algorithm computing f runs in polynomial time.

1.7

NP-completenesscompleteness proof structure

1.8

Circuit Satisfiability
ability Problem
Given
iven a Boolean combinational circuit composed of AND, OR, and NOT, is it satisfiable?
s
CIRCUIT-SAT={<C>:
SAT={<C>: C is a satisfiable Boolean circuit}

1.9

Formula Satisfiability Problem
We formulate the (formula) satisfiability
satis ability problem in terms of the language SAT as follows. An
instance of SAT is a Boolean
oolean formula φ composed of
1. n Boolean variables: x1, x2,..., xn;
2. m Boolean
oolean connectives: any Boolean function with one or two inputs and one output, such as ∧(AND), ∨ (OR), ¬ (NOT), → (implication), ↔ (if and only if); and3. parentheses. (Without loss of generality, we assume that there are no redundant parentheses,
i.e., there is at most one pair of parentheses per Boolean connective.)2

As in Boolean combinational circuits, a truth assignment for a Boolean formula φ is a set ofvalues for the variables of φ, and a satisfying assignment is a truth assignment that causes it toevaluate to 1. A formula with a satisfying assignment is a satisfiable formula. The satisfiability
problem asks whether a given Boolean formula is satisfiable; in formal-language terms,
SAT = {<φ> : φ is a satisfiable Boolean formula}As an example, the formulaφ = ((x1 → x2) ∨ ¬((¬x1 ↔ x3) ∨ x4)) ∧ ¬x2
has the satisfying assignment <x1 = 0, x2 = 0, x3 = 1, x4 = 1>, since
φ = ((0 → 0) ∨ ¬((¬0 ↔ 1) ∨ 1)) ∧ ¬0
= (1 ∨ ¬(1 ∨ 1)) ∧ 1= (1 ∨ 0) ∧ 1= 1,
and thus this formula φ belongs to SAT.
Theorem: Satisfiability of Boolean formulas is NP-complete.
Proof:
1. SAT ∈ NP.
To show that SAT belongs to NP, we show that a certificate consisting of a satisfying
assignment for an input formula φ can be verified in polynomial time. The verifying
algorithm simply replaces each variable in the formula with its corresponding value and thenevaluates the expression. This task is easily done in polynomial time. If the expression
evaluates to 1, the formula is satisfiable.
∴ SAT ∈ NP.
2. CIRCUIT-SAT ≤P SAT.
x1
x2

x4
x6

x3

x5

The figure above illustrates the basic idea of the reduction from CIRCUIT-SAT to SAT. For
each wire xi in the circuit C, the formula φ has a variable xi. The proper operation of a gate
can now be expressed as a formula involving the variables of its incident wires.
For example, the operation of the output of AND gate is x6 ↔ (x4 ∧ x5).
The formula φ produced by the reduction algorithm is the AND of the circuit-output variablewith the conjunction of clauses describing the operation of each gate.
For the circuit in the figure, the formula is
φ = x6 ∧ (x4 ↔ (x1 ∧ x2)) ∧ (x5 ↔ ¬x3)) ∧ (x6 ↔ (x4 ∧ x5))
Given a circuit C, it is straightforward to produce such a formula φ in polynomial time.
Now, circuit C is satisfiable exactly when the formula φ is satisfiable. If C has a satisfying
assignment, each wire of the circuit has a well-defined value, and the output of the circuit is 1.
Therefore, the assignment of wire values to variables in φ makes each clause of φ evaluate to1, and thus the conjunction of all evaluates to 1. Conversely, if there is an assignment thatcauses φ to evaluate to 1, the circuit C is satisfiable by an analogous argument.
Thus, we have shown that CIRCUIT-SAT ≤P SAT, which completes the proof.

3

1.10

3-CNF Satisfiability
Many problems can be proved NP-complete by reduction from formula satisfiability. The
reduction algorithm must handle any input formula, though, and this requirement can lead to a huge
number of cases that must be considered. It is often desirable, therefore, to reduce from a restrictedlanguage of Boolean formulas, so that fewer cases need be considered. Of course, we must not restrict
the language so much that it becomes polynomial-time solvable. One convenient language is 3-CNF
satisfiability, or 3-CNF-SAT.
We define 3-CNF satisfiability using the following terms. A literal in a Boolean formula is an
occurrence of a variable or its negation. A Boolean formula is in conjunctive normal form, or CNF, if
it is expressed as an AND of clauses, each of which is the OR of one or more literals. A Boolean
formula is in 3-conjunctive normal form, or 3-CNF, if each clause has exactly three distinct literals.
For example, the Boolean formula(x1 ∨ ¬x1 ∨ ¬x2) ∧ (x3 ∨ x2 ∨ x4) ∧ (¬x1 ∨ ¬x3 ∨ ¬x4)

is in 3-CNF. The first of its three clauses is (x1 ∨ ¬x1 ∨ ¬x2), which contains the three literals x,¬x, and ¬x.
1.11

The Clique Problem
A clique in an undirected graph G = (V, E) is a subset of vertices in V all connected to each otherby edges in E (i.e., forming a complete graph).
A
The size of a clique is the number of vertices it contains.
For example, in the graph beside, the nodes A, B and E forms a clique ofsize 3.

B

C

D

E

The clique problem is the optimization problem of finding a clique ofmaximum size in a graph. As a decision problem, we ask simply whether a clique of a given size kexists in the graph. The formal definition is:
CLIQUE = {<G, k> : G is a graph with a clique of size k}
Theorem: The clique problem is NP-complete.
Proof:
1. CLIQUE ∈ NP.

To show that CLIQUE ∈ NP, for a given graph G = (V, E), we use the set V' ⊆ V of vertices
in the clique as a certificate for G. Checking whether V' is a clique can be accomplished inpolynomial time by checking whether, for each pair u, v ∈ V', the edge (u, v) belongs to E.

2. 3-CNF-SAT ≤P CLIQUE.
The reduction algorithm begins with an instance of 3-CNF-SAT.
Let φ = C1 ∧ C2 ∧ … ∧ Ck be a Boolean formula in 3-CNF with k clauses.

For r = 1, 2, ..., k, each clause Cr has exactly three distinct literals  ,  and  .
We shall construct a graph G such that φ is satisfiable if and only if G has a clique of size k.
The graph G = (V, E) is constructed as follows. For each clause Cr =  ∨  ∨  in φ, weplace a triple of vertices ,andinto V. We put an edge between two vertices  and if both of the following hold:1.  and  are in different triples, that is, r ≠ s, and2. their corresponding literals are consistent, that is,  is not the negation of  .

This graph can easily be computed from φ in polynomial time. As an example of thisconstruction, if we have4

φ = (x1 ∨ ¬x2 ∨ ¬x3) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3),
then G is the graph shown in the following figure.

Now, we must show that this transformation of φ into G is a reduction.

[я  ,   p      ,        clause, clique-e iя ।e ,       ! , clause g  AND as।   , p% clause % 1   ,   i    satisfy    (satisfy        яl 1   )।  , %p ) clause- 1    ,    clause-e *) an, k e literal-e .)/ a0i 1   । g  p ) clause 2  exactly e    3 % %  corresponding literal-e.)/ 1 (e % % d  literal-e .)/ 1  2 , ,o  e%i % %)।  % %6.  g  clause, clique-e iя । e ,    p      ,e e clique, a2ৎ, e  3g p )  p )   2  k3।   , allpossible edge % % (g  9,  literal  complement literal-e  2  k
  ; a2ৎ x-e  2 ¬x  k   e edge  o   i)। s, g  k3। ae,e e clique  iя number of clause-e   ।u,  2g   u l. o    । a2ৎ, u,  p    %=    2  g e %। e g 2         । ei 2g  u l      ।  : g p%   3 яn corresponding e t clause-i ,o   ; , g  p )   3corresponding literal-e .)/ 1; s g  i %k e B    satisfied   g  iяB   number of clause-e   ।ei 2g  i %я  % i  । % C i  k /  o  ।]First, suppose that φ has a satisfying assignment. Then each clause Cr contains at least one
literal  that is assigned 1, and each such literal corresponds to a vertex  . Picking one such“true” literal from each clause yields a set V' of k vertices. We claim that V' is a clique. For
any two vertices  ,  ϵ V', where r ≠ s, both corresponding literals  and  are mapped to
1 by the given satisfying assignment, and thus the literals cannot be complements. Thus, by
the construction of G, the edge (  ,  ) belongs to E.
Conversely, suppose that G has a clique V' of size k. No edges in G connect vertices in thesame triple, and so V' contains exactly one vertex per triple. We can assign 1 to each literal such that  ϵ V' without fear of assigning 1 to both a literal and its complement, since G
contains no edges between inconsistent literals. Each clause is satisfied, and so φ is satisfied.
(Any variables that do not correspond to a vertex in the clique may be set arbitrarily.)[Note that a satisfying assignment of the formula has x2 = 0, x3 = 1, and x1 may be either 0 or
1 (don’t care). This assignment satisfies C1 with ¬x2, and it satisfies C2 and C3 with x3,
corresponding to the clique with lightly shaded vertices.]
5

1.12

The Vertex-Cover Problem
A vertex cover of an undirected graph G = (V, E) is a subset V' ⊆ Vsuch that if (u, v) ∈ E, then u ∈ V' or v ∈ V' (or both). That is, each vertex“covers” its incident edges, and a vertex cover for G is a set of vertices thatcovers all the edges in E.
The size of a vertex cover is the number of vertices in it.
For example, the graph in the figure beside has a vertex cover {w, z} of size 2.
The vertex-cover problem is to find a vertex cover of minimum size in a given graph. Restating
this optimization problem as a decision problem, we wish to determine whether a graph has a vertex
cover of a given size k. As a language, we define
VERTEX-COVER = {<G, k>: graph G has a vertex cover of size k}

1.13

The Hamiltonian Cycle Problem
A Hamiltonian cycle of a directed graph G = (V, E) is a simple cycle that contains each vertex inV.
The Hamiltonian cycle problem is to find an ordering of the vertices such that each vertex isvisited exactly once.

1.14

The Traveling-Salesman Problem
In the traveling-salesman problem, which is closely related to the Hamiltonian-cycle problem, asalesman must visit n cities. Modeling the problem as a complete graph with n vertices, we can saythat the salesman wishes to make a tour, or Hamiltonian cycle, visiting each city exactly once andfinishing at the city he starts from. There is an integer cost c(i, j ) to travel from city i to city j , andthe salesman wishes to make the tour whose total cost is minimum, where the total cost is the sum of
the individual costs along the edges of the tour. For example, in the figure below, a minimum-costtour is <u, w, v, x, u>, with cost 7. The formal language for the corresponding decision problem is
TSP ={<G, c, k>: G = (V, E) is a complete graph,c is a function from V × V → Z,k ∈ Z, andG has a traveling-salesman tour with cost at most k}
Theorem: The Traveling-Salesman problem is NP-complete.
Proof:
1. TSP ∈ NP.
Given an instance of the problem, we use as a certificate the sequence of n vertices in the
tour. The verification algorithm checks that this sequence contains each vertex exactly once,sums up the edge costs, and checks whether the sum is at most k. This process can certainly
be done in polynomial time.
2. HAM-CYCLE ≤P TSP.
Let G = (V, E) be an instance of HAM-CYCLE. We construct an instance of TSP as follows.
We form the complete graph G' = (V', E' ),where E' = {(i, j): i, j ∈ V and i ≠ j}, and we define
the cost function c by0  ,   ∈  c(i, j ) = 
1  ,   ∉ (Note that because G is undirected, it has no self-loops, andso c(v, v) = 1 for all vertices v ∈ V.) The instance of TSP isthen <G', c, 0>, which is easily formed in polynomial time.
[An example of this construction is shown in the figure]6

We now show that graph G has a Hamiltonian cycle if and only if graph G' has a tour of costat most 0.

[я  ,   p      , G g  Hamiltonian cycle 2  % o  % G'g   tour 2    E cost  0। e , G' g e .  F%     Gg  Hamiltonian cycle–e   edge
, G' g   edge-e cost 0। s, G g tour- G' g  0 cost-e execute   ।, %,G. ,   p      , G' g   E 0 cost-e tour   edge,cover  ,  edge  G g  edge।  / G' g   0  1 cost-e edge-i
i   tour-e cost 0     B tour-e  edge-e cost a0i 0    ।  0
cost-e edge g  pH, k G g  edge। s, G' g   E 0 cost-e tour  edge cover  ,  edge  G g  edge।
ei 2g  i %я  % i  । % C i  k /  o  ।]Suppose that graph G has a Hamiltonian cycle h. Each edge in h belongs to E and thus hascost 0 in G. Thus, h is a tour in G with cost 0.
Conversely, suppose that graph G has a tour h' of cost at most 0. Since the cost of the edges
in E' are 0 and 1, the cost of tour h' is exactly 0 and each edge on the tour must have cost 0.
Therefore, h' contains only edges in E. We conclude that h' is a Hamiltonian cycle in graphG.

7

APPROXIMATION ALGORITHMS
Concepts
2.1

Approaches to getting around NP-completeness Exponential time may be acceptable for small inputs [Brute Force] Isolate special cases that can run in polynomial time [DC, GRDY, DP] Near-optimal solutions may be acceptable [Approximation Algorithms]

2.2

Approximation Algorithms
An algorithm that returns near-optimal solutions is called an approximation algorithm.

2.3

Performance Ratios for Approximation Algorithms
Suppose that we are working on an optimization problem in which each potential solution has apositive cost, and we wish to find a near-optimal solution. Depending on the problem, an optimal
solution may be defined as one with maximum possible cost or one with minimum possible cost; thatis, the problem may be either a maximization or a minimization problem.
We say that an algorithm for a problem has an approximation ratio of ρ(n) if, for any input ofsize n, the cost C of the solution produced by the algorithm is within a factor of ρ(n) of the cost C* ofan optimal solution:max   ,   ≤ ρ(n)We also call an algorithm that achieves an approximation ratio of ρ(n) a ρ(n)-approximation
algorithm. The definitions of approximation ratio and of ρ(n)-approximation algorithm apply for bothminimization and maximization problems.
For a maximization problem, 0 < C ≤ C*, and the ratio C*/C gives the factor by which the cost of
an optimal solution is larger than the cost of the approximate solution.
Similarly, for a minimization problem, 0 < C* ≤ C, and the ratio C/C* gives the factor by which
the cost of the approximate solution is larger than the cost of an optimal solution.
Since all solutions are assumed to have positive cost, these ratios are always well defined. The
approximation ratio of an approximation algorithm is never less than 1, since C/C* < 1 implies C*/C >1. Therefore, a 1-approximation algorithm produces an optimal solution, and an approximation
algorithm with a large approximation ratio may return a solution that is much worse than optimal.
2.4

Approximation Algorithm for the Vertex-Cover Problem
Consider the graph beside. By inspection, theoptimal vertex cover is {b, d, e} and the size of
optimal solution, C* = 3.
An approximation algorithm for the vertex-coverproblem is as follows:
APPROX-VERTEX-COVER(G)
1 C←∅// C contains the result of vertex cover
2 E' ← E[G]// initially all edges are stored here
3 while E' ≠ ∅// all edges that are not considered yet
4
do let (u, v) be an arbitrary edge of E' // select an edge from E'
5
C ← C ∪ {u, v}// add vertices of the selected edge to C
6
remove from E' every edge incident on either u or v// delete all edges related to the vertices u and v
7 return C
8Applying this algorithm for the graph above, we get the following graph along with the vertex
cover (the initial contents of the array E' is also shown):
Analysis of the algorithmRunning time:




2.5

O(V+E): if we use adjacency list.

2-Approximation Algorithm
Minimization problem; C* = 3; C = 6

Factor = C/C* = 2

Theorem: APPROX-VERTEX-COVER is a polynomial-time 2-approximation algorithm   =  e p   , C/C* = 2। e , general-.  C  C*-e     , ?
   я    optimal solution 2 C*-e  / e e minimization problem, s,% m    , । i  2 eo      , approximate solution 2 C-e   E   ,  (worst case % C     )। e d     яn C  C*- edge-e  2 mk/ 2 i vertex cover   CM %। CM ,  p ) e edge %[p2 % C*-e  % m    , । *%, p )  e   edge % i,   Aa)   %। e , no two edges in A share an endpoint। ( , (a, b) edge %A-   A-
  edge 2  ,    a a2 b ।) , e edge  o  , approximation
algorithm-e NO i an  edge-e B edge-e endpoint
,  edge-  % i % । s, Ae *)    3 u l 2 , g  unique। , e %      , C*-e e%  3 A-ee%* edge- .  ।  , C*-e a0i A-e p ) edge-e яn  , k e%    3
2 ।   C*-e    |C*| ≥ |A|।e % C-e   E    , । approximation algorithm an G A-  e edge  o  ,   яn C- d   3  o   ।   C-e  E    ,  |C| = 2A।||e d   combine   ,o   : |#| ≤ 2 ]The loop on lines 3–6 repeatedly picks an edge (u, v) from E', adds its endpoints u and v to C, anddeletes all edges in E' that are covered by either u or v. The running time of this algorithm is O(V + E),
using adjacency lists to represent E'. Therefore, APPROX-VERTEX-COVER runs in polynomial
time.
The set C of vertices that is returned by APPROX-VERTEX-COVER is a vertex cover, since thealgorithm loops until every edge in E[G] has been covered by some vertex in C.
To see that APPROX-VERTEX-COVER returns a vertex cover that is at most twice the size ofan optimal cover, let A denote the set of edges that were picked in line 4 of APPROX-VERTEXCOVER. In order to cover the edges in A, any vertex cover — in particular, an optimal cover C* —must include at least one endpoint of each edge in A. No two edges in A share an endpoint, since oncean edge is picked in line 4, all other edges that are incident on its endpoints are deleted from E' in line
6. Thus, no two edges in A are covered by the same vertex from C*, and we have the lower bound:|C*| ≥ |A| …(1) on the size of an optimal vertex cover.
Each execution of line 4 picks an edge for which neither of its endpoints is already in C, yielding
an upper bound (an exact upper bound, in fact) on the size of the vertex cover returned:|C| = 2 |A| …(2)Combining equations (1) and (2), we obtain|C| = 2 |A|≤ 2 |C*| ,thereby proving the theorem.
9