! b) The feedback edge problem: given a graph G and an integer fe, does G have a set of fc edges such that every cycle of G contains at least one of the к edges?

! c) The linear integer programming problem: given a set of luiear constraints of the form JJL UiXi < сот ii i where the as and с are integer constants and rci, ,..., a: are variables, does there exist an assignment of integers to each of the variables that makes all the constraints true?

! d) The dominating-set problem: given a graph G and an integer k, does there exist a subset S of к nodes of G such that each node is either in S or adjacent to a node of 5?

e) The firehouse problem: given a graph G, a distance d, and a budget / of firehouses, is it possible to choose / nodes of G such that no node is of distance (number of edges that must be traversed) greater than d from some firehouse?

*! f) The half-clique problem: Given a graph G with an even number of vertices, does there exist a clique of G (see Exercise 10.4,1) consisting of exactly half the nodes of G? Hint: Reduce CLIQUE to the half-clique problem. You must figure out how to add nodes to adjust the size of the largest clique.

!! g) The unit-execution-time-scheduling problem: given A: tasks

TuT2,...,Tk

a number of processors p, a time limit t, and some precedence constraints of the form Tj < Tj between pairs of tasks, does there exist a schedule of the tasks, such that:

1. Each task is assigned to one time unit between 1 and t,

2. At most p tasks are assigned to any one time unit, and

3. The precedence constraints are respected; that is, if T,; < is a constrahit, then Ti is assigned to an earlier time unit than Tj?

!! h) The exact-cover problem: given a set S and a set of subsets Si,S2,. ,3 of S, is there a set of sets Г С {Sl, 5з,..., 5} such that each element x of 5 is in exactly one member of Г?

!! i) The knapsack problem: given a list of к integers iij, -ik, can we partition them into two sets whose sums are the same? Note: This problem appears superficially to be in P, since you might assume that the integers themselves are small. Indeed, if the values of the integers are limited to some polynomial in the number of integers k, then there is a polynomial-time algorithm. However, in a list of fc integers represented in binary, having total length n, we can have certain integers whose values are almost exponential in n.

Exercise 10.4.5: A Hamilton path in a graph G is an ordering of all the nodes rii, 712,..., rijt such that there is an edge from тц to m+i, for all г = 1,2,..., A-1. A directed Hamilton path is the same for a directed graph; there must be an arc from each щ to щ+у. Notice that the Hamilton path requirement is just slightly weaker than the Hamilton-circuit condition, If we also required an edge or arc from Пк to Til, then it would be exactly the Hamilton-circuit condition. The (directed) Hamilton-path problem is: given a (directed) graph, does it have at least one (directed) Hamilton path?

* a) Prove that the directed Hamilton-path problem is NP-complete, Hint: Perform a reduction from DHC. Pick any node, and split it into two, such that these two nodes must be the endpoints of a directed Hamilton path, and such a path exists if and only if the original graph has a directed Hamilton circuit.

b) Show that the (undirected) Hamilton-path problem is NP-complete. Hint: Adapt the construction of Theorem 10,23,

*! c) Show that the following problem is NP-complete: given a graph G and an integer k, does G have a spanning tree with at most к leaf vertices? Hint: Perform a reduction from the HamUton-path problem,

! d) Show that the following problem is NP-complete: given a graph G and an integer d, does G have a spanning tree with no node of degree greater than di (The degree of a node n in the spanning tree is the number of edges of the tree that have n as an end.)

10.5 Summary of Chapter 10

4 The Classes V and HV\ V consists of all those languages or problems accepted by some Turing machine that runs in some polynomial amount of time, as a function of its input length. MV is the class of languages or problems that are accepted by nondeterministic TMs with a polynomial bound on the time taken along any sequence of nondeterministic choices.

4 The V = MV Question: It is unknown whether or not V and MV are really the same classes of languages, although we suspect strongly that there are languages in MP that are not in P.

4 Polynomial-Time Reductions: If we can transform instances of one problem in polynomial time into instances of a second problem that has the same answer - yes or no - then we say the first problem is polynomial-time reducible to the second.

♦ NP-Complete Problems: A language is NP-complete if it is in MP, and there is a polynomial-time reduction from each language in MP to the language in question. We believe strongly that none of the NP-complete

10.6. REFERENCES FOR CHAPTER 10 467

problems are in P, and the fact that no one has ever found a polynomial-time algorithm for any of the thousands of known NP-complete problems is mutually re-enforcing evidence that none are in V.

NP-Complete Satisfiability Problems: Cooks theorem showed the first NP-complete problem - whether a boolean expression is satisfiable - by reducing all problems in AfP to the SAT problem in polynomial time. In addition, the problem remains NP-complete even if the expression is restricted to consist of a product of clauses, each of which consists of only three literals - the problem 3SAT.

4 Other NP-Complete Problems: There is a vast collection of known NP-complete problems; each is proved NP-complete by a polynomial-time reduction from some previously known NP-complete problem. We have given reductions that show the following problems NP-complete: independent set, node cover, directed and undirected versions of the Hamilton circuit problem, and the travehng-salesman problem.

10.6 References for Chapter 10

The concept of NP-completeness as evidence that the problem could not be solved in polynomial time, as well as the proof that SAT, CSAT, and 3SAT are NP-complete, comes from Cook [3]. A follow-on paper by Karp [6] is generally accorded equal importance, because that paper showed that NP-completeness was not just an isolated phenomenon, but rather applied to very many of the hard combinatorial problems that people m Operations Research and other disciplines had been studying for years. Each of the problems proved NP-complete in Section 10.4 are from that paper: mdependent set, node cover, Hamilton circuit, and TSP. In addition, we can fuid there the solutions to several of the problems mentioned in the exercises: clique, edge cover, knapsack, coloring, and exact-cover.

The book by Garey and Johnson [4] summarizes a great deal about what is known concerning which problems are NP-complete, and special cases that are polynomial-time. In [5] are articles about approximating the solution to an NP-complete problem in polynomial time.

Several other contributions to the theory of NP-completeness should be acknowledged. The study of classes of languages defined by the running time of Turing machines began with Hartmanis and Stearns [8]. Cobham [2] was the first to isolate the concept of the class P, as opposed to algorithms that had a particular polynomial running time, such as O(n). Levin [7] was an independent, although somewhat later, discovery of the NP-completeness idea.

NP-completeness of luiear integer programming [Exercise 10.4.4(c)] appears in [1] and also in unpublished notes of J. Gathen and M. Sieveking. NP-completeness of unit-execution-time scheduling [Exercise 10.4.4(g)] is from [9].