# CHAPTER 36: NP-COMPLETENESS

The subject of this chapter, however, is an interesting class of problems, called the "NP-complete" problems, whose status is unknown. No polynomial-time algorithm has yet been discovered for an NP-complete problem, nor has anyone yet been able to prove a superpolynomial-time lower bound for any of them. This so-called P NP question has been one of the deepest, most perplexing open research problems in theoretical computer science since it was posed in 1971.

Most theoretical computer scientists believe that the NP-complete problems are intractable. The reason is that if any single NP-complete problem can be solved in polynomial time, then every NP-complete problem has a polynomial-time algorithm. Given the wide range of NP-complete problems that have been studied to date, without any progress toward a polynomial-time solution, it would be truly astounding if all of them could be solved in polynomial time.

To become a good algorithm designer, you must understand the rudiments of the theory of NP-completeness. If you can establish a problem as NP-complete, you provide good evidence for its intractability. As an engineer, you would then do better spending your time developing an approximation algorithm (see Chapter 37) rather than searching for a fast algorithm that solves the problem exactly. Moreover, many natural and interesting problems that on the surface seem no harder than sorting, graph searching, or network flow are in fact NP-complete. Thus, it is important to become familiar with this remarkable class of problems.

This chapter studies the aspects of NP-completeness that bear most directly on the analysis of algorithms. In Section 36.1, we formalize our notion of "problem" and define the complexity class P of polynomial-time solvable decision problems. We also see how these notions fit into the framework of formal-language theory. Section 36.2 defines the class NP of decision problems whose solutions can be verified in polynomial time. It also formally poses the P NP question.

Section 36.3 shows how relationships between problems can be studied via polynomial-time "reductions." It defines NP-completeness and sketches a proof that one problem, called "circuit satisfiability," is NP-complete. Having found one NP-complete problem, we show in Section 36.4 how other problems can be proven to be NP-complete much more simply by the methodology of reductions. The methodology is illustrated by showing that two formula-satisfiability problems are NP-complete. A variety of other problems are shown to be NP-complete in Section 36.5.

# 36.1 Polynomial time

We begin our study of NP-completeness by formalizing our notion of polynomial-time solvable problems. These problems are generally regarded as tractable. The reason why is a philosophical, not a mathematical, issue. We can offer three supporting arguments.

First, although it is reasonable to regard a problem that requires time (n100) as intractable, there are very few practical problems that require time on the order of such a high-degree polynomial. The polynomial-time computable problems encountered in practice typically require much less time.

Second, for many reasonable models of computation, a problem that can be solved in polynomial time in one model can be solved in polynomial time in another. For example, the class of problems solvable in polynomial time by the serial random-access machine used throughout most of this book is the same as the class of problems solvable in polynomial time on abstract Turing machines.1 It is also the same as the class of problems solvable in polynomial time on a parallel computer, even if the number of processors grows polynomially with the input size.

1See Hopcroft and Ullman [104] or Lewis and Papadimitriou [139] for a thorough treatment of the Turing-machine model. of calls to polynomial-time subroutines, the running time of the composite algorithm is polynomial.

Third, the class of polynomial-time solvable problems has nice closure properties, since polynomials are closed under addition, multiplication, and composition. For example, if the output of one polynomial-time algorithm is fed into the input of another, the composite algorithm is polynomial. If an otherwise polynomial-time algorithm makes a constant number of calls to polynomial-time subroutines, the running time of the composite algorithm is polynomial.

## Abstract problems

Although the theory of NP-completeness compels us to recast optimization problems as decision problems, this requirement does not diminish the impact of the theory. In general, if we can solve an optimization problem quickly, we can also solve its related decision problem quickly. We simply compare the value obtained from the solution of the optimization problem with the bound provided as input to the decision problem. If an optimization problem is easy, therefore, its related decision problem is easy as well. Stated in a way that has more relevance to NP-completeness, if we can provide evidence that a decision problem is hard, we also provide evidence that its related optimization problem is hard. Thus, even though it restricts attention to decision problems, the theory of NP-completeness applies much more widely.

## Encodings

2 The codomain of e need not be binary strings; any set of strings over a finite alphabet having at least 2 symbols will do.

We can use encodings to map abstract problems to concrete problems. Given an abstract decision problem Q mapping an instance set I to {0, 1}, an encoding e : I {0, 1}* can be used to induce a related concrete decision problem, which we denote by e(Q). If the solution to an abstract-problem instance i I is Q(i) {0, 1}, then the solution to the concrete-problem instance e(i) {0, 1}* is also Q(i). As a technicality, there may be some binary strings that represent no meaningful abstract-problem instance. For convenience, we shall assume that any such string is mapped arbitrarily to 0. Thus, the concrete problem produces the same solutions as the abstract problem on binary-string instances that represent the encodings of abstract-problem instances.

The encoding of an abstract problem is therefore quite important to our understanding of polynomial time. We cannot really talk about solving an abstract problem without first specifying an encoding. Nevertheless, in practice, if we rule out "expensive" encodings such as unary ones, the actual encoding of a problem makes little difference to whether the problem can be solved in polynomial time. For example, representing integers in base 3 instead of binary has no effect on whether a problem is solvable in polynomial time, since an integer represented in base 3 can be converted to an integer represented in base 2 in polynomial time.

Let Q be an abstract decision problem on an instance set I, and let e1 and e2 be polynomially related encodings on I. Then, e1(Q) P if and only if e2(Q) P.

Proof We need only prove the forward direction, since the backward direction is symmetric. Suppose, therefore, that e1(Q) can be solved in time O(nk) for some constant k. Further, suppose that for any problem instance i, the encoding e1(i) can be computed from the encoding e2(i) in time O(nc) for some constant c, where n = |e1(i)|. To solve problem e2(Q), on input e2(i), we first compute e1(i) and then run the algorithm for e1(Q) on e1(i). How long does this take? The conversion of encodings takes time O(nc), and therefore |e1(i)| = O(nc), since the output of a serial computer cannot be longer than its running time. Solving the problem on e1 (i) takes time O(|e1(i)|k) = O(nck), which is polynomial since both c and k are constants.

Thus, whether an abstract problem has its instances encoded in binary or base 3 does not affect its "complexity," that is, whether it is polynomial-time solvable or not, but if instances are encoded in unary, its complexity may change. In order to be able to converse in an encoding-independent fashion, we shall generally assume that problem instances are encoded in any reasonable, concise fashion, unless we specifically say otherwise. To be precise, we shall assume that the encoding of an integer is polynomially related to its binary representation, and that the encoding of a finite set is polynomially related to its encoding as a list of its elements, enclosed in braces and separated by commas. (ASCII is one such encoding scheme.) With such a "standard" encoding in hand, we can derive reasonable encodings of other mathematical objects, such as tuples, graphs, and formulas. To denote the standard encoding of an object, we shall enclose the object in angle braces. Thus, G denotes the standard encoding of a graph G.

As long as we implicitly use an encoding that is polynomially related to this standard encoding, we can talk directly about abstract problems without reference to any particular encoding, knowing that the choice of encoding has no effect on whether the abstract problem is polynomial-time solvable. Henceforth, we shall generally assume that all problem instances are binary strings encoded using the standard encoding, unless we explicitly specify the contrary. We shall also typically neglect the distinction between abstract and concrete problems. The reader should watch out for problems that arise in practice, however, in which a standard encoding is not obvious and the encoding does make a difference.

## A formal-language framework

`L = {x1x2 : x1  L1 and x2  L2} .`

`L* = {}  L  L2 L3   . .  ,`

where Lk is the language obtained by concatenating L to itself k times.

From the point of view of language theory, the set of instances for any decision problem Q is simply the set *, where = {0, 1}. Since Q is entirely characterized by those problem instances that produce a 1 (yes) answer, we can view Q as a language L over = {0, 1}, where

`L = {x  * : Q(x) = 1} .`

For example, the decision problem PATH has the corresponding language

`PATH = {G,u,v,k : G = (V,E) is an undirected graph,`

`u,v  V,`

`k  0 is an integer, and`

`there exists a path from u to v in G`

`whose length is at most k}.`

(Where convenient, we shall sometimes use the same name--PATH in this case--to refer to both a decision problem and its corresponding language.)

As an example, the language PATH can be accepted in polynomial time. One polynomial-time accepting algorithm computes the shortest path from u to v in G, using breadth-first search, and then compares the distance obtained with k. If the distance is at most k, the algorithm outputs 1 and halts. Otherwise, the algorithm runs forever. This algorithm does not decide PATH, however, since it does not explicitly output 0 for instances in which the shortest path has length greater than k. A decision algorithm for PATH must explicitly reject binary strings that do not belong to PATH. For a decision problem such as PATH, such a decision algorithm is easy to design. For other problems, such as Turing's Halting Problem, there exists an accepting algorithm, but no decision algorithm exists.

Using this language-theoretic framework, wee can provide an alternative definition of the complexity class P:

`P = {L  {0,1}* : there exists an algorithm A`

`that decides L in polynomial time} .`

In fact, P is also the class of languages that can be accepted in polynomial time.

P = {L : L is accepted by a polynomial-time algorithm} .

Proof Since the class of languages decided by polynomial-time algorithms is a subset of the class of languages accepted by polynomial-time algorithms, we need only show that if L is accepted by a polynomial-time algorithm, it is decided by a polynomial-time algorithm. Let L be the language accepted by some polynomial-time algorithm A. We shall use a classic "simulation" argument to construct another polynomial-time algorithm A' that decides L. Because A accepts L in time O(nk) for some constant k, there also exists a constant c such that A accepts L in at most T = cnk steps. For any input string x, the algorithm A' simulates the action of A for time T. At the end of time T, algorithm A' inspects the behavior of A. If A has accepted x, then A' accepts x by outputting a 1. If A has not accepted x, then A' rejects x by outputting a 0. The overhead of A' simulating A does not increase the running time by more than a polynomial factor, and thus A' is a polynomial-time algorithm that decides L.

Note that the proof of Theorem 36.2 is nonconstructive. For a given language L P, we may not actually know a bound on the running time for the algorithm A that accepts L. Nevertheless, we know that such a bound exists, and therefore, that an algorithm A' exists that can check the bound, even though we may not be able to find the algorithm A' easily.

## Exercises

Give a formal encoding of directed graphs as binary strings using an adjacency-matrix representation. Do the same using an adjacency-list representation. Argue that the two representations are polynomially related.

Suppose that a language L can accept any string x L in polynomial time, but that the algorithm that does this runs in superpolynomial time if x L. Argue that L can be decided in polynomial time.

Show that an algorithm that makes at most a constant number of calls to polynomial-time subroutines runs in polynomial time, but that a polynomial number of calls to polynomial-time subroutines may result in an exponential-time algorithm.

Show that the class P, viewed as a set of languages, is closed under union, intersection, concatenation, complement, and Kleene star. That is, if Ll, L2 P, then Ll L2 P, etc.

# 36.2 Polynomial-time verification

## Hamiltonian cycles

`HAM-CYCLE = {G : G is a hamiltonian graph} .`

How might an algorithm decide the language HAM-CYCLE? Given a problem instance G, one possible decision algorithm lists all permutations of the vertices of G and then checks each permutation to see if it is a hamiltonian path. What is the running time of this algorithm? If we use the "reasonable" encoding of a graph as its adjacency matrix, the number m of vertices in the graph is , where n = |G| is the length of the encoding of G. There are m! possible permutations of the vertices, and therefore the running time is , which is not O(nk) for any constant k. Thus, this naive algorithm does not run in polynomial time, and in fact, the hamiltonian-cycle problem is NP-complete, as we shall prove in Section 36.5.

## Verification algorithms

Consider a slightly easier problem, however. Suppose that a friend tells you that a given graph G is hamiltonian, and then offers to prove it by giving you the vertices in order along the hamiltonian cycle. It would certainly be easy enough to verify the proof: simply verify that the provided cycle is hamiltonian by checking whether it is a permutation of the vertices of V and whether each of the consecutive edges along the cycle actually exists in the graph. This verification algorithm can certainly be implemented to run in O(n2) time, where n is the length of the encoding of G . Thus, a proof that a hamiltonian cycle exists in a graph can be verified in polynomial time.

`L = {x  {0, 1}* : there exists y {0, 1}* such that A(x, y) = 1} .`

Intuitively, an algorithm A verifies a language L if for any string x L, there is a certificate y that A can use to prove that x L. Moreover, for any string x L there must be no certificate proving that x L. For example, in the hamiltonian-cycle problem, the certificate is the list of vertices in the hamiltonian cycle. If a graph is hamiltonian, the hamiltonian cycle itself offers enough information to verify this fact. Conversely, if a graph is not hamiltonian, there is no list of vertices that can fool the verification algorithm into believing that the graph is hamiltonian, since the verification algorithm carefully checks the proposed "cycle" to be sure.

## The complexity class NP

`L = {x  {0,1}* : there exists a certificate y with |y| = 0(|x|c)`

`such that A(x,y) = 1} .`

We say that algorithm A verifies language L in polynomial time.

From our earlier discussion on the hamiltonian-cycle problem, it follows that HAM-CYCLE NP. (It is always nice to know that an important set is nonempty.) Moreover, if L P, then L NP, since if there is a polynomial-time algorithm to decide L, the algorithm can be easily converted to a two-argument verification algorithm that simply ignores any certificate and accepts exactly those input strings it determines to be in L. Thus, P NP.

It is unknown whether P = NP, but most researchers believe that P and NP are not the same class. Intuitively, the class P consists of problems that can be solved quickly. The class NP consists of problems for which a solution can be verified quickly. You may have learned from experience that it is often more difficult to solve a problem from scratch than to verify a clearly presented solution, especially when working under time constraints. Theoretical computer scientists generally believe that this analogy extends to the classes P and NP, and thus that NP includes languages that are not in P.

There is more compelling evidence that P NP--the existence of "NP-complete" languages. We shall study this class in Section 36.3.

Thus, our understanding of the precise relationship between P and NP is woefully incomplete. Nevertheless, by exploring the theory of NP-completeness, we shall find that our disadvantage in proving problems to be intractable is, from a practical point of view, not nearly so great as we might suppose.

## Exercises

Prove that if G is an undirected bipartite graph with an odd number of vertices, then G is nonhamiltonian.

Show that if HAM-CYCLE P, then the problem of listing the vertices of a hamiltonian cycle, in order, is polynomial-time solvable.

Prove that the class NP of languages is closed under union, intersection, concatenation, and Kleene star. Discuss the closure of NP under complement.

Show that any language in NP can be decided by an algorithm running in time 2O(nk) for some constant k.

Show that the hamiltonian-path problem can be solved in polynomial time on directed acyclic graphs. Give an efficient algorithm for the problem.

Prove that P co-NP.

Prove that if NP co-NP, then P NP.

Let G be a connected, undirected graph with at least 3 vertices, and let G3 be the graph obtained by connecting all pairs of vertices that are connected by a path in G of length at most 3. Prove that G3 is hamiltonian. (Hint: Construct a spanning tree for G, and use an inductive argument.)

# 36.3 NP-completeness and reducibility

Perhaps the most compelling reason why theoretical computer scientists believe that P NP is the existence of the class of "NP-complete" problems. This class has the surprising property that if any one NP-complete problem can be solved in polynomial time, then every problem in NP has a polynomial-time solution, that is, P = NP. Despite years of study, though, no polynomial-time algorithm has ever been discovered for any NP-complete problem.

The language HAM-CYCLE is one NP-complete problem. If we could decide HAM-CYCLE in polynomial time, then we could solve every problem in NP in polynomial time. In fact, if NP - P should turn out to be nonempty, we could say with certainty that HAM-CYCLE NP - P.

#### Figure 36.3 An illustration of a polynomial-time reduction from a language L1 to a language L2 via a reduction function f. For any input x {0, 1}*, the question of whether x L1 has the same answer as the question of whether f(x) L2.

The NP-complete languages are, in a sense, the "hardest" languages in NP. In this section, we shall show how to compare the relative "hardness" of languages using a precise notion called "polynomial-time reducibility." First, we formally define the NP-complete languages, and then we sketch a proof that one such language, called CIRCUIT-SAT, is NP-complete. In Section 36.5, shall use the notion of reducibility to show that many other problems are NP-complete.

## Reducibility

`x  L1 if and only if f(x)  L2 .`

#### (36.1)

Figure 36.3 illustrates the idea of a polynomial-time reduction from a language L1 to another language L2. Each language is a subset of {0, 1}*. The reduction function f provides a polynomial-time mapping such that if x L1, then f(x) L2. Moreover, if x L1, then f(x) L2. Thus, the reduction function maps any instance x of the decision problem represented by the language L1 to an instance f(x) of the problem represented by L2. Providing an answer to whether f(x) L2 directly provides the answer to whether x L1.

#### Figure 36.4 The proof of Lemma 36.3. The algorithm F is a reduction algorithm that computes the reduction function f from L1 to L2 in polynomial time, and A2 is a polynomial-time algorithm that decides L2. Illustrated is an algorithm A1 that decides whether x L1 by using F to transform any input x into f(x) and then using A2 to decide whether f(x) L2.

Polynomial-time reductions give us a powerful tool for proving that various languages belong to P.

If L1, L2 {0, 1}* are languages such that L1 L2, then L2 P implies L1 P.

Proof Let A2 be a polynomial-time algorithm that decides L2, and let F be a polynomial-time reduction algorithm that computes the reduction function f. We shall construct a polynomial-time algorithm A1 that decides L1.

Figure 36.4 illustrates the construction of A1. For a given input x {0, 1}*, the algorithm A1 uses F to transform x into f(x), and then it uses A2 to test whether f(x) L2. The output of A2 is the value provided as the output from A1.

The correctness of A1 follows from condition (36.1). The algorithm runs in polynomial time, since both F and A2 run in polynomial time (see Exercise 36.1-6).

## NP-completeness

A language L {0, 1}* is NP-complete if

1. L NP, and

2. L' p L for every L' NP.

#### Figure 36.5 How most theoretical computer scientists view the relationships among P, NP, and NPC. Both P and NPC are wholly contained within NP, and .

As the following theorem shows, NP-completeness is at the crux of deciding whether P is in fact equal to NP.

If any NP-complete problem is polynomial-time solvable, then P = NP. If any problem in NP is not polynomial-time solvable, then all NP-complete problems are not polynomial-time solvable.

Proof Suppose that L P and also that L NPC. For any L' NP, we have L' p L by property 2 of the definition of NP-completeness. Thus, by Lemma 36.3, we also have that L' P, which proves the first statement of the lemma.

To prove the second statement, suppose that there exists an L NP such that L P. Let L' NPC be any NP-complete language, and for the purpose of contradiction, assume that L' P. But then, by Lemma 36.3, we have L p L', and thus L P.

It is for this reason that research into the P NP question centers around the NP-complete problems. Most theoretical computer scientists believe that P NP, which leads to the relationships among P, NP, and NPC shown in Figure 36.5. But for all we know, someone may come up with a polynomial-time algorithm for an NP-complete problem, thus proving that P = NP. Nevertheless, since no polynomial-time algorithm for any NP-complete problem has yet been discovered, a proof that a problem is NP-compete provides excellent evidence for its intractability.

## Circuit satisfiability

#### Figure 36.6 Two instances of the circuit-satisfiability problem. (a) The assignment x1 = 1, x2 = 1, x3 = 0 to the inputs of this circuit causes the output of the circuit to be 1. The circuit is therefore satisfiable. (b) No assignment to the inputs of this circuit can cause the output of the circuit to be 1. The circuit is therefore unsatisfiable.

Unfortunately, the formal proof that the circuit-satisfiability problem is NP-complete requires technical detail beyond the scope of this text. Instead, we shall informally describe a proof that relies on a basic understanding of boolean combinational circuits. This material is reviewed at the beginning of Chapter 29.

The circuit-satisfiability problem is, "Given a boolean combinational circuit composed of AND, OR, and NOT gates, is it satisfiable?" In order to pose this question formally, however, we must agree on a standard encoding for circuits. One can devise a graphlike encoding that maps any given circuit C into a binary string C whose length is not much larger than the size of the circuit itself. As a formal language, we can therefore define

`CIRCUIT-SAT =`

`{C : C is a satisfiable boolean combinational circuit} .`

The circuit-satisfiability problem has great importance in the area of computer-aided hardware optimization. If a circuit always produces 0, it can be replaced by a simpler circuit that omits all logic gates and provides the constant 0 value as its output. A polynomial-time algorithm for the problem would have considerable practical application.

Given a circuit C, we might attempt to determine whether it is satisfiable by simply checking all possible assignments to the inputs. Unfortunately, if there are k inputs, there are 2k possible assignments. When the size of C is polynomial in k, checking each one leads to a superpolynomial-time algorithm. In fact, as has been claimed, there is strong evidence that no polynomial-time algorithm exists that solves the circuit-satisfiability problem because circuit satisfiability is NP-complete. We break the proof of this fact into two parts, based on the two parts of the definition of NP-completeness.

The circuit-satisfiability problem belongs to the class NP.

Proof We shall provide a two-input, polynomial-time algorithm A that can verify CIRCUIT-SAT. One of the inputs to A is (a standard encoding of) a boolean combinational circuit C. The other input is a certificate corresponding to an assignment of boolean values to the wires in C.

The algorithm A is constructed as follows. For each logic gate in the circuit, it checks that the value provided by the certificate on the output wire is correctly computed as a function of the values on the input wires. Then, if the output of the entire circuit is 1, the algorithm outputs 1, since the values assigned to the inputs of C provide a satisfying assignment. Otherwise, A outputs 0.

Whenever a satisfiable circuit C is input to algorithm A, there is a certificate whose length is polynomial in the size of C and that causes A to output a 1. Whenever an unsatisfiable circuit is input, no certificate can fool A into believing that the circuit is satisfiable. Algorithm A runs in polynomial time: with a good implementation, linear time suffices. Thus, CIRCUIT-SAT can be verified in polynomial time, and CIRCUIT-SAT NP.

The second part of proving that CIRCUIT-SAT is NP-complete is to show that the language is NP-hard. That is, we must show that every language in NP is polynomial-time reducible to CIRCUIT-SAT. The actual proof of this fact is full of technical intricacies, and so we shall settle for a sketch of the proof based on some understanding of the workings of computer hardware.

A computer program is stored in the computer memory as a sequence of instructions. A typical instruction encodes an operation to be performed, addresses of operands in memory, and an address where the result is to be stored. A special memory location, called the program counter, keeps track of which instruction is to be executed next. The program counter is automatically incremented whenever an instruction is fetched, thereby causing the computer to execute instructions sequentially. The execution of an instruction can cause a value to be written to the program counter, however, and then the normal sequential execution can be altered, allowing the computer to loop and perform conditional branches.

At any point during the execution of a program, the entire state of the computation is represented in the computer's memory. (We take the memory to include the program itself, the program counter, working storage, and any of the various bits of state that a computer maintains for bookkeeping.) We call any particular state of computer memory a configuration. The execution of an instruction can be viewed as mapping one configuration to another. Importantly, the computer hardware that accomplishes this mapping can be implemented as a boolean combinational circuit, which we denote by M in the proof of the following lemma.

The circuit-satisfiability problem is NP-hard.

Proof Let L be any language in NP. We shall describe a polynomial-time algorithm F computing a reduction function â that maps every binary string x to a circuit C = â(x) such that x L if and only if C CIRCUIT-SAT.

Since L NP, there must exist an algorithm A that verifies L in polynomial-time. The algorithm F that we shall construct will use the two-input algorithm A to compute the reduction function â.

Let T(n) denote the worst-case running time of algorithm A on length-n input strings, and let k 1 be a constant such that T(n) = O(nk) and the length of the certificate is O(nk). (The running time of A is actually a polynomial in the total input size, which includes both an input string and a certificate, but since the length of the certificate is polynomial in the length n of the input string, the running time is polynomial in n.)

The basic idea of the proof is to represent the computation of A as a sequence of configurations. As shown in Figure 36.7, each configuration can be broken into parts consisting of the program for A, the program counter and auxiliary machine state, the input x, the certificate y, and working storage. Starting with an initial configuration c0, each configuration ci is mapped to a subsequent configuration ci+1 by the combinational circuit M implementing the computer hardware. The output of the algorithm A--0 or 1--is written to some designated location in the working storage when A finishes executing, and if we assume that thereafter A halts, the value never changes. Thus, if the algorithm runs for at most T(n) steps, the output appears as one of the bits in cT(n).

#### Figure 36.7 The sequence of configurations produced by an algorithm A running on an input x and certificate y. Each configuration represents the state of the computer for one step of the computation and, besides A, x, and y, includes the program counter (PC), auxiliary machine state, and working storage. Except for the certificate y, the initial configuration c0 is constant. Each configuration is mapped to the next configuration by a boolean combinational circuit M. The output is a distinguished bit in the working storage.

The reduction algorithm F constructs a single combinational circuit that computes all configurations produced by a given initial configuration. The idea is to paste together T(n) copies of the circuit M. The output of the ith circuit, which produces configuration ci, is fed directly into the input of the (i + 1)st circuit. Thus, the configurations, rather than ending up in a state register, simply reside as values on the wires connecting copies of M.

Recall what the polynomial-time reduction algorithm F must do. Given an input x, it must compute a circuit C = â(x) that is satisfiable if and only if there exists a certificate y such that A(x, y) = 1. When F obtains an input x, it first computes n = |x| and constructs a combinational circuit C' consisting of T(n) copies of M. The input to C' is an initial configuration corresponding to a computation on A(x, y), and the output is the configuration cT(n).

The circuit C = â(x) that F computes is obtained by modifying C' slightly. First, the inputs to C' corresponding to the program for A, the initial program counter, the input x, and the initial state of memory are wired directly to these known values. Thus, the only remaining inputs to the circuit correspond to the certificate y. Second, all outputs to the circuit are ignored, except the one bit of cT(n) corresponding to the output of A. This circuit C, so constructed, computes C(y) = A(x, y) for any input y of length O(nk). The reduction algorithm F, when provided an input string x, computes such a circuit C and outputs it.

Two properties remain to be proved. First, we must show that F correctly computes a reduction function â. That is, we must show that C is satisfiable if and only if there exists a certificate y such that A(x, y) = 1. Second, we must show that F runs in polynomial time.

To show that F correctly computes a reduction function, let us suppose that there exists a certificate y of length O(nk) such that A(x, y) = 1. Then, if we apply the bits of y to the inputs of C, the output of C is C(y) = A(x, y) = 1. Thus, if a certificate exists, then C is satisfiable. For the other direction, suppose that C is satisfiable. Hence, there exists an input y to C such that C(y) = 1, from which we conclude that A(x, y) = 1. Thus, F correctly computes a reduction function.

To complete the proof, we need only show that F runs in time polynomial in n = |x|. The first observation we make is that the number of bits required to represent a configuration is polynomial in n. The program for A itself has constant size, independent of the length of its input x. The length of the input x is n, and the length of the certificate y is O(nk). Since the algorithm runs for at most O(nk) steps, the amount of working storage required by A is polynomial in n as well. (We assume that this memory is contiguous; Exercise 36.3-4 asks you to extend the argument to the situation in which the locations accessed by A are scattered across a much larger region of memory and the particular pattern of scattering can differ for each input x.)

The combinational circuit M implementing the computer hardware has size polynomial in the length of a configuration, which is polynomial in O(nk) and hence is polynomial in n. (Most of this circuitry implements the logic of the memory system.) The circuit C consists of at most t = O(nk) copies of M, and hence it has size polynomial in n. The construction of C from x can be accomplished in polynomial time by the reduction algorithm F, since each step of the construction takes polynomial time.

The language CIRCUIT-SAT is therefore at least as hard as any language in NP, and since it belongs to NP, it is NP-complete.

The circuit-satisfiability problem is NP-complete.

Proof Immediate from Lemmas 36.5 and 36.6 and the definition of NP-completeness.

## Exercises

Show that the p relation is a transitive relation on languages. That is, show that if L1 p L2 and L2 p L3, then L1 p L3.

Prove that if and only if .

Show that a satisfying assignment can be used as a certificate in an alternative proof of Lemma 36.5. Which certificate makes for an easier proof?

The proof of Lemma 36.6 assumes that the working storage for algorithm A occupies a contiguous region of polynomial size. Where in the proof is this assumption exploited? Argue that this assumption does not involve any loss of generality.

Show that L is complete for NP if and only if is complete for co-NP.

The reduction algorithm F in the proof of Lemma 36.6 constructs the circuit C = f(x) based on knowledge of x, A, and k. Professor Sartre observes that the string x is input to F, but only the existence of A and k is known to F (since the language L belongs to NP), not their actual values. Thus, the professor concludes that F can't possibly construct the circuit C and that the language CIRCUIT-SAT is not necessarily NP-hard. Explain the flaw in the professor's reasoning.

# 36.4 NP-completeness proofs

The following lemma is the basis of our method for showing that a language is NP-complete.

If L is a language such that L' p L for some L' NPC, then L is NP-hard. Moreover, if L NP, then L NPC.

Proof Since L' is NP-complete, for all L\" NP, we have L\" p L'. By supposition, L' p L, and thus by transitivity (Exercise 36.3-1), we have L\" p L, which shows that L is NP-hard. If L NP, we also have L NPC.

In other words, by reducing a known NP-complete language L' to L, we implicitly reduce every language in NP to L. Thus, Lemma 36.8 gives us a method for proving that a language L is NP-complete:

1. Prove L NP.

2. Select a known NP-complete language L'.

3. Describe an algorithm that computes a function f mapping every instance of L' to an instance 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.

This methodology of reducing from a single known NP-complete language is far simpler than the more complicated process of providing reductions from every language in NP. Proving CIRCUIT-SAT NPC has given us a "foot in the door." Knowing that the circuit-satisfiability problem is NP-complete now allows us to prove much more easily that other problems are NP-complete. Moreover, as we develop a catalog of known NP-complete problems, applying the methodology will become that much easier.

## Formula satisfiability

1. boolean variables: x1, x2, . . . . ;

3. parentheses.

`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 ,`

#### (36.2)

and thus this formula belongs to SAT.

The naive algorithm to determine whether an arbitrary boolean formula is satisfiable does not run in polynomial time. There are 2n possible assignments in a formula with n variables. If the length of is polynomial in n, then checking every assignment requires superpolynomial time. As the following theorem shows, a polynomial-time algorithm is unlikely to exist.

#### Figure 36.8 Reducing circuit satisfiability to formula satisfiability. The formula produced by the reduction algorithm has a variable for each wire in the circuit.

Satisfiability of boolean formulas is NP-complete.

Proof We shall argue first that SAT NP. Then, we shall show that CIRCUIT-SAT p SAT; by Lemma 36.8, this will prove the theorem.

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 then evaluates the expression, much as we did in equation (36.2) above. This task is easily doable in polynomial time. If the expression evaluates to 1, the formula is satisfiable. Thus, the first condition of Lemma 36.8 for NP-completeness holds.

To prove that SAT is NP-hard, we show that CIRCUIT-SAT p SAT. In other words, any instance of circuit satisfiability can be reduced in polynomial time to an instance of formula satisfiability. Induction can be used to express any boolean combinational circuit as a boolean formula. We simply look at the gate that produces the circuit output and inductively express each of the gate's inputs as formulas. The formula for the circuit is then obtained by writing an expression that applies the gate's function to its inputs' formulas.

Unfortunately, this straightforward method does not constitute a polynomial-time reduction. Shared subformulas can cause the size of the generated formula to grow exponentially (see Exercise 36.4-1). Thus, the reduction algorithm must be somewhat more clever.

Figure 36.8 illustrates the basic idea of the reduction from CIRCUIT-SAT to SAT on the circuit from Figure 36.6(a). 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 AND gate is x10 (x7 x8 x9).

The formula produced by the reduction algorithm is the AND of the circuit-output variable with the conjunction of clauses describing the operation of each gate. For the circuit in the figure, the formula is

`  =  x10  (x4  x3)`

` (x5  (x1  x2))`

` (x6  x4)`

` (x7  (x1  x2  x4))`

` (x8  (x5  x6))`

` (x9  (x6  x7))`

` (x10  (x7  x8  x9)) .`

Given a circuit C, it is straightforward to produce such a formula in polynomial time.

Why is the circuit 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 to 1, and thus the conjunction of all evaluates to 1. Conversely, if there is an assignment that causes 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-CNF satisfiability

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 x1, x1, and x2.

In 3-CNF-SAT, we are asked whether a given boolean formula in 3-CNF is satisfiable. The following theorem shows that a polynomial-time algorithm that can determine the satisfiability of boolean formulas is unlikely to exist, even when they are expressed in this simple normal form.

` = ((x1  x2)  ((x1  x3)  x4))  x2 .`

#### Figure 36.9 The tree corresponding to the formula

Satisfiability of boolean formulas in 3-conjunctive normal form is NP-complete.

Proof The argument we used in the proof of Theorem 36.9 to show that SAT NP applies equally well here to show that 3-CNF-SAT NP. Thus, we need only show that 3-CNF-SAT is NP-hard. We prove this by showing that SAT p 3-CNF-SAT, from which the proof will follow by Lemma 36.8.

The reduction algorithm can be broken into three basic steps. Each step progressively transforms the input formula closer to the desired 3-conjunctive normal form.

` = ((x1  x2)  ((x1  x3)  x4))  x2 .`

#### (36.3)

Should the input formula contain a clause such as the OR of several literals, associativity can be used to parenthesize the expression fully so that every internal node in the resulting tree has 1 or 2 children. The binary parse tree can now be viewed as a circuit for computing the function.

Mimicking the reduction in the proof of Theorem 36.9, we introduce a variable yi for the output of each internal node. Then, we rewrite the original formula as the AND of the root variable and a conjunction of clauses describing the operation of each node. For the formula (36.3), the resulting expression is

`' = y1  (y1  (y2  x2))`

` (y2  (y3  y4))`

` (y3  (x1  x2))`

` (y4  y5)`

` (y5  (y6  y4))`

` (y6  (x1  x3)).`

Observe that the formula ' thus obtained is a conjunction of clauses , each of which has at most 3 literals. The only additional requirement is that each clause be an OR of literals.

`y1  y2  x2  (y1  (y2  x2))`

`------------------------------`

`1   1   1           0`

`1   1   0           1`

`1   0   1           0`

`1   0   0           0`

`0   1   1           1`

`0   1   0           0`

`0   0   1           1`

`0   0   0           1`

#### Figure 36.10 The truth table for the clause (y1 (y2 x2)).

In our example, we convert the clause into CNF as follows. The truth table for 'i is given in Figure 36.10. The DNF formula equivalent to

`(y1  y2  x2)  (y1  y2  x2)  (y1  y2  x2)  (y1  y2  x2) .`

Applying DeMorgan's laws, we get the CNF formula

which is equivalent to the original clause .

Each clause of the formula ' has now been converted into a CNF formula , and thus ' is equivalent to the CNF formula \" consisting of the conjunction of the . Moreover, each clause of \" has at most 3 literals.

The third and final step of the reduction further transforms the formula so that each clause has exactly 3 distinct literals. The final 3-CNF formula ''' is constructed from the clauses of the CNF formula \". It also uses two auxiliary variables that we shall call p and q. For each clause Ci of \", we include the following clauses in ''':

If Ci has 3 distinct literals, then simply include Ci as a clause of '''.

If Ci has 2 distinct literals, that is, if Ci = (l1 l2), where l1 and l2 are literals, then include (l1 l2 p) (l1 l2 p) as clauses of f(). The literals p and p merely fulfill the syntactic requirement that there be exactly 3 distinct literals per clause: (l1 l2 p) (l1 l2 p) is equivalent to (l1 l2) whether p = 0 or p = 1.

If Ci has just 1 distinct literal l, then include (l p q) (l p q) (l p q) (l p q) as clauses of '''. Note that every setting of p and q causes the conjunction of these four clauses to evaluate to l.

We can see that the 3-CNF formula ''' is satisfiable if and only if is satisfiable by inspecting each of the three steps. Like the reduction from CIRCUIT-SAT to SAT, the construction of ' from in the first step preserves satisfiability. The second step produces a CNF formula \" that is algebraically equivalent to '. The third step produces a 3-CNF formula ''' that is effectively equivalent to \", since any assignment to the variables p and q produces a formula that is algebraically equivalent to \".

We must also show that the reduction can be computed in polynomial time. Constructing ' from introduces at most 1 variable and 1 clause per connective in . Constructing \" from ' can introduce at most 8 clauses into \" for each clause from ', since each clause of ' has at most 3 variables, and the truth table for each clause has at most 23 = 8 rows. The construction of ''' from \" introduces at most 4 clauses into ''' for each clause of \". Thus, the size of the resulting formula ''' is polynomial in the length of the original formula. Each of the constructions can easily be accomplished in polynomial time.

## Exercises

Consider the straightforward (nonpolynomial-time) reduction in the proof of Theorem 36.9. Describe a circuit of size n that, when converted to a formula by this method, yields a formula whose size is exponential in n.

Show the 3-CNF formula that results when we use the method of Theorem 36.10 on the formula (36.3).

Show that the problem of determining the satisfiability of boolean formulas in disjunctive normal form is polynomial-time solvable.

Suppose that someone gives you a polynomial-time algorithm to decide formula satisfiability. Describe how to use this algorithm to find satisfying assignments in polynomial time.

# 36.5 NP-complete problems

NP-complete problems arise in diverse domains: boolean logic, graphs, arithmetic, network design, sets and partitions, storage and retrieval, sequencing and scheduling, mathematical programming, algebra and number theory, games and puzzles, automata and language theory, program optimization, and more. In this section, we shall use the reduction methodology to provide NP-completeness proofs for a variety of problems drawn from graph theory and set partitioning.

Figure 36.11 outlines the structure of the NP-completeness proofs in this section and Section 36.4. Each language in the figure is proved NP-complete by reduction from the language that points to it. At the root is CIRCUIT-SAT, which we proved NP-complete in Theorem 36.7.

## 36.5.1 The clique problem

`CLIQUE = {G,k: G is a graph with a clique of size k}.`

A naive algorithm for determining whether a graph G = (V, E) with |V| vertices has a clique of size k is to list all k-subsets of V, and check each one to see whether it forms a clique. The running time of this algorithm is , which is polynomial if k is a constant. In general, however, k could be proportional to |V|, in which case the algorithm runs in superpolynomial time. As one might suspect, an efficient algorithm for the clique problem is unlikely to exist.

Proof 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 in polynomial time by checking whether, for every pair u, v V', the edge (u, v) belongs to E.

We next show that the clique problem is NP-hard by proving that 3-CNF-SAT p CLIQUE. That we should be able to prove this result is somewhat surprising, since on the surface logical formulas seem to have little to do with graphs.

#### Figure 36.12 The graph G derived from the 3-CNF formula = C1 C2 C3, where C1 = (x1 x2 x3), C2 =(x1 x2 x3), and C3 = (x1 x2 x3), in reducing 3-CNF-SAT to CLIQUE. A satisfying assignment of the formula is x1 = 0, x2 = 0, x3 = 1. This satisfying assignment satisfies C1 with x2, and it satisfies C2 and C3 with x3, corresponding to the clique with lightly shaded vertices.

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 . 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 in , we place a triple of vertices in V. We put an edge between two vertices if both of the following hold:

are in different triples, that is, r s, and

This graph can easily be computed from in polynomial time. As an example of this construction, if we have

` = (x1  x2  x3)  (x1  x2  x3)  (x1  x2  x3) ,`

then G is the graph shown in Figure 36.12.

We must show that this transformation of into G is a reduction. 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 of V' of k vertices. We claim that V' is a clique. For any two vertices , where r s, both corresponding literals 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.

#### Figure 36.13 Reducing CLIQUE to VERTEX-COVER. (a) An undirected graph G = (V,E) with clique V' = {u,v,x,y}. (b) The graph produced by the reduction algorithm that has vertex cover V - V' = {w,z}.

Conversely, suppose that G has a clique V' of size k. No edges in G connect vertices in the same triple, and so V' contains exactly one vertex per triple. We can assign 1 to each literal such that 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 satisfied. (Any variables that correspond to no vertex in the clique may be set arbitrarily.)

In the example of Figure 36.12, a satisfying assignment of is x1 = 0, x2 = 0, x3 = 1. A corresponding clique of size k = 3 consists of the vertices corresponding to x2 from the first clause, x3 from the second clause, and x3 from the third clause.

## 36.5.2 The vertex-cover problem

`VERTEX-COVER = {G, k: graph G has vertex cover of size k} .`

The following theorem shows that this problem is NP-complete.

The vertex-cover problem is NP-complete.

Proof We first show that VERTEX-COVER NP. Suppose we are given a graph G = (V, E) and an integer k. The certificate we choose is the vertex cover V' V itself. The verification algorithm affirms that |V'| = k, and then it checks, for each edge (u, v) E, whether u V' or v V'. This verification can be performed straightforwardly in polynomial time.

The reduction algorithm takes as input an instance G, k of the clique problem. It computes the complement , which is easily doable in polynomial time. The output of the reduction algorithm is the instance , of the vertex-cover problem. To complete the proof, we show that this transformation is indeed a reduction: the graph G has a clique of size k if and only if the graph has a vertex cover of size |V| - k.

Suppose that G has a clique V' V with |V'| = k. We claim that V - V' is a vertex cover in . Let (u, v) be any edge in . Then, (u, v) E, which implies that at least one of u or v does not belong to V', since every pair of vertices in V' is connected by an edge of E. Equivalently, at least one of u or v is in V - V', which means that edge (u,v) is covered by V - V'. Since (u, v) was chosen arbitrarily from , every edge of is covered by a vertex in V - V'. Hence, the set V - V', which has size |V| - k, forms a vertex cover for .

Conversely, suppose that has a vertex cover V' V , where |V'| = |V| - k. Then, for all u, v V, if (u, v) , if , then u V' or v V' or both. The contrapositive of this implication is that for all u, v V, if u V' and v V', then (u, v) E. In other words, V - V' is a clique, and it has size |V| - |V'| = k.

Since VERTEX-COVER is NP-complete, we don't expect to find a polynomial-time algorithm for finding a minimum-size vertex cover. Section 37.1 presents a polynomial-time "approximation algorithm," however, which produces "approximate" solutions for the vertex-cover problem. The size of a vertex cover produced by the algorithm is at most twice the minimum size of a vertex cover.

Thus, we shouldn't give up hope just because a problem is NP-complete. There may be a polynomial-time approximation algorithm that obtains near-optimal solutions, even though finding an optimal solution is NP-complete. Chapter 37 gives several approximation algorithms for NP-complete problems.

## 36.5.3 The subset-sum problem

As usual, we define the problem as a language:

`SUBSET-SUM =`

`{S, t: there exists a subset S'  S such that t = sS'S} .`

As with any arithmetic problem, it is important to recall that our standard encoding assumes that the input integers are coded in binary. With this assumption in mind, we can show that the subset-sum problem is unlikely to have a fast algorithm.

The subset-sum problem is NP-complete.

Proof To show that SUBSET-SUM is in NP, for an instance S, t of the problem, we let the subset S' be the certificate. Checking whether t = sS's can be accomplished by a verification algorithm in polynomial time.

We now show that VERTEX-COVER P SUBSET-SUM. Given an instance G, k of the vertex-cover problem, the reduction algorithm constructs an instance S, t of the subset-sum problem such that G has a vertex cover of size k if and only if there is a subset of S whose sum is exactly t.

For example, Figure 36.14(b) shows the incidence matrix for the undirected graph of Figure 36.14(a). The incidence matrix is shown with lower-indexed edges on the right, rather than on the left as is conventional, in order to simplify the formulas for the numbers in S.

Given a graph G and an integer k, the reduction algorithm computes a set S of numbers and an integer t. To understand how the reduction algorithm works, let us represent numbers in a "modified base-4" fashion. The |E| low-order digits of a number will be in base-4 but the high-order digit can be as large as k. The set of numbers is constructed in such a way that no carries can be propagated from lower digits to higher digits.

#### Figure 36.14 The reduction of the vertex-cover problem to the subset-sum problem. (a) An undirected graph G. A vertex cover {v1, v3, v4} of size 3 is lightly shaded. (b) The corresponding incidence matrix. Shading of the rows corresponds to the vertex cover of part (a). Each edge ej has a 1 in at least one lightly shaded row. (c) The corresponding subset-sum instance. The portion within the box is the incidence matrix. Here, the vertex cover {v1, v3, v4} of size k = 3 corresponds to the lightly shaded subset {1, 16, 64, 256, 1040, 1093, 1284}, which adds up to 3754.

The set S consists of two types of numbers, corresponding to vertices and edges respectively. For each vertex vi V, we create a positive integer xi whose modified base-4 representation consists of a leading 1 followed by |E| digits. The digits correspond to vi's row of the incidence matrix B = (bij) for G, as illustrated in Figure 36.14(c). Formally, for i = 0, 1, . . . , |V| - 1,

For each edge ej E, we create a positive integer yj that is just a row of the "identity" incidence matrix. (The identity incidence matrix is the |E| |E| matrix with 1's only in the diagonal positions.) Formally, for j = 0, 1, . . . , |E| - 1,

`yj = 4j .`

The first digit of the target sum t is k, and all |E| lower-order digits are 2's. Formally,

All of these numbers have polynomial size when we represent them in binary. The reduction can be performed in polynomial time by manipulating the bits of the incidence matrix.

We must now show that graph G has a vertex cover of size k if and only if there is a subset S' S whose sum is t. First, suppose that G has a vertex cover V' V of size k. Let V' = {vi1, vi2, . . . , vik}, and define S' by

`S' = {xi1, xi2, . . . , xik} `

`{yj : ej is incident on precisely one vertex in V'} .`

To see that sS'S = t, observe that summing the k leading 1's of the xim S' gives the leading digit k of the modified base-4 representation of t. To get the low-order digits of t, each of which is a 2, consider the digit positions in turn, each of which corresponds to an edge ej. Because V' is a vertex cover, ej is incident on at least one vertex in V'. Thus, for each edge ej, there is at least one xim S' with a 1 in the jth position. If ej is incident on two vertices in V', then both contribute a 1 to the sum in the jth position. The jth digit of yj contributes nothing, since ej is incident on two vertices, which implies that yj S'. Thus, in this case, the sum of S' produces a 2 in the jth position of t. For the other case--when ej is incident on exactly one vertex in V'--we have yj S', and the incident vertex and yj each contribute 1 to the sum of the jth digit of t, thereby also producing a 2. Thus, S' is a solution to the subset-sum instance S.

Now, suppose that there is a subset S' S that sums to t. Let S = {xi1, xi2, . . . , xim} {yj1, yj2, . . . , yjp}. We claim that m = k and that V' = {vi1, vi2, . . . , vim} is a vertex cover for G. To prove this claim, we start by observing that for each edge ej E, there are three 1's in set S in the ej position: one from each of the two vertices incident on ej, and one from yj. Because we are working with a modified base-4 representation, there are no carries from position ej to position ej+1. Thus, for each of the |E| low-order positions of t, at least one and at most two xi must contribute to the sum. Since at least one xi contributes to the sum for each edge, we see that V' is a vertex cover. To see that m = k, and thus that V' is a vertex cover of size k, observe that the only way the leading k in target t can be achieved is by including exactly k of the xi in the sum.

In Figure 36.14, the vertex cover V' = {v1, v3, v4} corresponds to the subset S' = {x1, x3, x4, y0, y2, y3, y4}. All of the yj are included in S', with the exception of y1, which is incident on two vertices in V'.

## 36.5.4 The hamiltonian-cycle problem

#### Figure 36.15 (a) Widget A, used in the reduction from 3-CNF-SAT to HAM-CYCLE. (b)-(c) If A is a subgraph of some graph G that contains a hamiltonian cycle and the only connections from A to the rest of G are through the vertices a, a', b, and b', then the shaded edges represent the only two possible ways in which the hamiltonian cycle may traverse the edges of subgraph A. (d) A compact representation of the A widget.

The hamiltonian cycle problem is NP-complete.

Proof We first show that HAM-CYCLE belongs to NP. Given a graph G = (V, E), our certificate is the sequence of |V| vertices that make up the hamiltonian cycle. The verification algorithm checks that this sequence contains each vertex in V exactly once and that with the first vertex repeated at the end, it forms a cycle in G. This verification can be performed in polynomial time.

Our first widget is the subgraph A shown in Figure 36.15(a). Suppose that A is a subgraph of some graph G and that the only connections between A and the remainder of G are through the vertices a, a', b, and b'. Furthermore, suppose that graph G has a hamiltonian cycle. Since any hamiltonian cycle of G must pass through vertices z1, z2, z3, and z4 in one of the ways shown in Figures 36.15(b) and (c), we may treat subgraph A as if it were simply a pair of edges (a, a') and (b, b') with the restriction that any hamiltonian cycle of G must include exactly one of these edges. We shall represent widget A as shown in Figure 36.15(d).

The subgraph B in Figure 36.16 is our second widget. Suppose that B is a subgraph of some graph G and that the only connections from B to the remainder of G are through vertices b1, b2, b3, and b4. A hamiltonian cycle of graph G cannot traverse all of the edges (b1, b2), (b2, b3), and (b3, b4), since then all vertices in the widget other than b1, b2, b3, and b4 would be missed. A hamiltonian cycle of G may, however, traverse any proper subset of these edges. Figures 36.16(a)-(e) show five such subsets; the remaining two subsets can be obtained by performing a top-to-bottom flip of parts (b) and (e). We represent this widget as in Figure 36.16(f), the idea being that at least one of the paths pointed to by the arrows must be taken by a hamiltonian cycle.

The graph G that we shall construct consists mostly of copies of these two widgets. The construction is illustrated in Figure 36.17. For each of the k clauses in , we include a copy of widget B, and we join these widgets together in series as follows. Letting bij be the copy of vertex bj in the ith copy of widget B, we connect bi,4 to bi+1,1 for i = 1, 2, . . . , k - 1.

Then, for each variable xm in , we include two vertices . We connect these two vertices by means of two copies of the edge , which we denote by em and to distinguish them. The idea is that if the hamiltonian cycle takes edge em, it corresponds to assigning variable xm the value 1. If the hamiltonian cycle takes edge , the variable is assigned the value 0. Each pair of these edges forms a two-edge loop; we connect these small loops in series by adding edges for m = 1, 2, . . . , n - 1. We connect the left (clause) side of the graph to the right (variable) side by means of two edges , which are the topmost and bottommost edges in Figure 36.17.

We are not yet finished with the construction of graph G, since we have yet to relate the variables to the clauses. If the jth literal of clause Ci is xm, then we use an A widget to connect edge (bij, bi,j+1) with edge em. If the jth literal of clause Ci is xm, then we instead put an A widget between edge (bij, bi,j+1) and edge . In Figure 36.17, for example, because clause C2 is (x1 x2 x3), we place three A widgets as follows:

between (b2,1, b2,2) and e1,

between (b2,2, b2,3) and , and

between (b2,3, b2,4) and e3.

Note that connecting two edges by means of A widgets actually entails replacing each edge by the five edges in the top or bottom of Figure 36.15(a) and, of course, adding the connections that pass through the z vertices as well. A given literal lm may appear in several clauses (xm in Figure 36.17, for example), and thus an edge em or may be be influenced by several A widgets (edge , for example). In this case, we connect the A widgets in series, as shown in Figure 36.18, effectively replacing edge em or by a series of edges.

#### Figure 36.18 The actual construction used when an edge em or is influenced by multiple A widgets. (a) A portion of Figure 36.17. (b) The actual subgraph constructed.

We claim that formula is satisfiable if and only if graph G contains a hamiltonian cycle. We first suppose that G has a hamiltonian cycle h and show that is satisfiable. Cycle h must take a particular form:

First, it traverses edge to go from the top left to the top right.

It then follows all of the vertices from top to bottom, choosing either edge em or edge , but not both.

It next traverses edge to get back to the left side.

Finally, it traverses the B widgets from bottom to top on the left.

(It actually traverses edges within the A widgets as well, but we use these subgraphs to enforce the either/or nature of the edges it connects.)

Given the hamiltonian cycle h, we define a truth assignment for as follows. If edge em belongs to h, then we set xm = 1. Otherwise, edge belongs to h, and we set xm = 0.

We claim that this assignment satisfies . Consider a clause Ci and the corresponding B widget in G. Each edge (bi,jbi,j+l) is connected by an A widget to either edge em or edge , depending on whether xm or xm is the jth literal in the clause. The edge (bi,j,bi,j+1) is traversed by h if and only if the corresponding literal is 0. Since each of the three edges (bi,1,bi,2),(bi,2,bi,3),(bi,3,bi,4) in clause Ci is also in a B widget, all three cannot be traversed by the hamiltonian cycle h. One of the three edges, therefore, must have a corresponding literal whose assigned value is 1, and clause Ci is satisfied. This property holds for each clause Ci, i = 1, 2, . . . , k, and thus formula ø is satisfied.

#### Figure 36.19 An instance of the traveling-salesman problem. Shaded edges represent a minimum-cost tour, with cost 7.

Conversely, let us suppose that formula ø is satisfied by some truth assignment. By following the rules from above, we can construct a hamiltonian cycle for graph G: traverse edge em if xm = 1, traverse edge if xm = 0, and traverse edge (bi,j,bi,j+1) if and only if the jth literal of clause Ci is 0 under the assignment. These rules can indeed be followed, since we assume that s is a satisfying assignment for formula ø.

Finally, we note that graph G can be constructed in polynomial time. It contains one B widget for each of the k clauses in ø. There is one A widget for each instance of each literal in ø, and so there are 3k A widgets. Since the A and B widgets are of fixed size, the graph G has O(k) vertices and edges and is easily constructed in polynomial time. Thus, we have provided a polynomial-time reduction from 3-CNF-SAT to HAM-CYCLE.

## 36.5.5 The traveling-salesman problem

`TSP = {G,c,k : G = (V,E) is a complete graph,`

`c is a function from V  V  Z,`

`k  Z, and`

`G has a traveling-salesman tour with cost at most k} .`

The following theorem shows that a fast algorithm for the traveling-salesman problem is unlikely to exist.

The traveling-salesman problem is NP-complete.

Proof We first show that TSP belongs to 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.

To prove that TSP is NP-hard, we show that 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 we define the cost function c by

The instance of TSP is then (G', c, 0), which is easily formed in polynomial time.

We now show that graph G has a hamiltonian cycle if and only if graph G' has a tour of cost at most 0. Suppose that graph G has a hamiltonian cycle h. Each edge in h belongs to E and thus has cost 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 costs of the edges in E' are 0 and 1, the cost of tour h' is exactly 0. Therefore, h' contains only edges in E. We conclude that h is a hamiltonian cycle in graph G.

## Exercises

Professor Marconi proclaims that the subgraph used as widget A in the proof of Theorem 36.14 is more complicated than necessary: vertices z3 and z4 of Figure 36.15(a) and the vertices above and below them are not needed. Is the professor correct? That is, does the reduction work with this smaller version of the widget, or does the "either/or" property of the widget disappear?

# Problems

a. Formulate a related decision problem for the independent-set problem, and prove that it is NP-complete. (Hint: Reduce from the clique problem.)

b. Suppose that you are given a subroutine to solve the decision problem you defined in part (a). Give an algorithm to find an independent set of maximum size. The running time of your algorithm should be polynomial in |V| and |E|, where queries to the black box are counted as a single step.

Although the independent-set decision problem is NP-complete, certain special cases are polynomial-time solvable.

c. Give an efficient algorithm to solve the independent-set problem when each vertex in G has degree 2. Analyze the running time, and prove that your algorithm works correctly.

d. Give an efficient algorithm to solve the independent-set problem when G is bipartite. Analyze the running time, and prove that your algorithm works correctly. (Hint: Use the results of Section 27.3.)

#### Figure 36.20 The widget corresponding to a clause (x V y V z), used in Problem 36-2.

a. Give an efficient algorithm to determine a 2-coloring of a graph if one exists.

b. Cast the graph-coloring problem as a decision problem. Show that your decision problem is solvable in polynomial time if and only if the graph-coloring problem is solvable in polynomial time.

To prove that 3-COLOR is NP-complete, we use a reduction from 3-CNF-SAT. Given a formula ø of m clauses on n variables x1, x2, . . . , xn, we construct a graph G = (V,E) as follows. The set V consists of a vertex for each variable, a vertex for the negation of each variable, 5 vertices for each clause, and 3 special vertices: TRUE, FALSE, and RED. The edges of the graph are of two types: "literal" edges that are independent of the clauses and "clause" edges that depend on the clauses. The literal edges form a triangle on the special vertices and also form a triangle on xi, xi, and RED for i = 1, 2, . . . , n.

d. Argue that in any 3-coloring c of a graph containing the literal edges, exactly one of a variable and its negation is colored c(TRUE) and the other is colored c(FALSE). Argue that for any truth assignment for ø, there is a 3-coloring of the graph containing just the literal edges.

The widget shown in Figure 36.20 is used to enforce the condition corresponding to a clause (x V y V z). Each clause requires a unique copy of the 5 vertices that are heavily shaded in the figure; they connect as shown to the literals of the clause and the special vertex TRUE.

e. Argue that if each of x, y, and z is colored c(TRUE) or c(FALSE), then the widget is 3-colorable if and only if at least one of x, y, or z is colored c(TRUE).

f. Complete the proof that 3-COLOR is NP-complete.

# Chapter notes

Garey and Johnson [79] provide a wonderful guide to NP-completeness, discussing the theory at length and providing a catalogue of many problems that were known to be NP-complete in 1979. (The list of NP-complete problem domains at the beginning of Section 36.5 is drawn from their table of contents.) Hopcroft and Ullman [104] and Lewis and Papadimitriou [139] have good treatments of NP-completeness in the context of complexity theory. Aho, Hopcroft, and Ullman [4] also cover NP-completeness and give several reductions, including a reduction for the vertex-cover problem from the hamiltonian-cycle problem.

The class P was introduced in 1964 by Cobham [44] and, independently, in 1965 by Edmonds [61], who also introduced the class NP and conjectured that P NP. The notion of NP-completeness was proposed in 1971 by Cook [49], who gave the first NP-completeness proofs for formula satisfiability and 3-CNF satisfiability. Levin [138] independently discovered the notion, giving an NP-completeness proof for a tiling problem. Karp [116] introduced the methodology of reductions in 1972 and demonstrated the rich variety of NP-complete problems. Karp's paper included the original NP-completeness proofs of the clique, vertex-cover, and hamiltonian-cycle problems. Since then, hundreds of problems have been proven to be NP-complete by many researchers.

The proof of Theorem 36.14 was adapted from Papadimitriou and Steiglitz [154].