10.4 Additional NP-Complete Problems

We shall now give you a small sample of the process whereby one NP-complete problem leads to proofs that other problems are also NP-complete. This process of discovering new NP-complete problems has two important effects:

When we discover a problem to be NP-complete, it tells us that there is little chance an efficient algorithm can be developed to solve it. We are encouraged to look for heuristics, partial solutions, approximations, or other ways to avoid attacking the problem head-on. Moreover, we can do so with confidence that we are not just missing the trick.

Each time we add a new NP-complete problem P to the list, we re-enforce the idea that all NP-complete problems require exponential time. The effort that has undoubtedly gone into finding a polynomial-time algorithm for problem P was, unknowingly, effort devoted to showing P = AfP. It is the accumulated weight of the unsuccessful attempts by many skilled scientists and mathematicians to show something that is tantamount to V = that ultimately convinces us that it is very unlikely that V -ЯР, but rather that all the NP-complete problems require exponential time.

In this section, we meet several NP-complete problems involving graphs. These problems are among those graph problems most commonly used in the solution to questions of practical importance. We shall talk about the Traveling Salesman problem (TSP), which we met earlier in Section 10.1.4. We shall show that a simpler, and also important version, called the Hamilton-Circuit problem (HC), is NP-complete, thus showing that the more general TSP is NP-complete. We introduce several other problems involving covering, of graphs, such as the node-cover problem, which asks us to find the smallest set of nodes that cover all the edges, in the sense that at least one end of every edge is in the selected set.

10.4.1 Describing NP-complete Problems

As we introduce new NP-complete problems, we shall use a stylized form of definition, as follows:

1. The name of the problem, and usually an abbreviation, like 3SAT or TSP.

2. The input to the problem: what is represented, and how.

3. The output desired: under what circumstances should the output be yes ?

4. The problem from which a reduction is made to prove the problem NP-complete.

Example 10.16: Here is how the description of the problem 3SAT and its proof of NP-completeness might look:

PROBLEM: Satisfiability for 3-CNF expressions (3SAT).

INPUT: A boolean expression in 3-CNF.

OUTPUT: Yes if and only if the expression is satisfiable.

REDUCTION FROM: CSAT. □

10.4.2 The Problem of Independent Sets

Let G be an undirected graph. We say a subset / of the nodes of G is an independent set if no two nodes of I are connected by an edge of G. An independent set is maximal if it is as large (has as many nodes) as any independent set for the same graph.

Example 10.17: In the graph of Fig. 10.1 (See Section 10.1.2), {1,4} is a maximal uidependent set. It is the only set of size two that is independent, because there is an edge between any other pair of nodes. Thus, no set of size three or more is independent; for instance, {1,2,4} is not independent because there is an edge between 1 and 2. Thus, {1,4} is a maximal independent set. In fact, it is the only maximal independent set for this graph, although in general a graph may have many maximal independent sets. As another example, {1} is an independent set for this graph, but not maximal, □

In combinatorial optimization, the maximal-independent-set problem is usually stated as: given a graph, find a maximal independent set. However, as with all problems in the theory of intractable problems, we need to state our problem in yes/no terms. Thus, we need to introduce a lower bound into the statement of the problem, and we phrase the question as whether a given graph has an independent set at least as large as the bound. The formal definition of the raaximal-independent-set problem is:

PROBLEM: Independent Set (IS).

INPUT: A graph G and a lower bound k, which must be between 1 and the number of nodes of G.

OUTPUT: Yes if and only if G has an independent set of к nodes, REDUCTION FROM: 3SAT.

We must prove IS to be NP-complete by a polynomial-time reduction froni 3SAT, as promised. That reduction is in the next theorem.

Theorem 10.18: The independent-set problem is NP-complete.

PROOF: First, it is easy to see that IS is in AfP. Given a graph G and a bound k, guess к nodes and check that they are independent.

Now, let us show how to perform the reduction of 3SAT to IS. Let E - (ei)(e2) (em) be a 3-CNF expression. We construct firom E a graph G with 3m nodes, which we shall give the names where 1 < г < m and j = 1,2, or 3. The node represents the jth literal in the clause е . Figure 10.8 is an example of a graph G, based on the 3-CNF expression

{xi -\-X2+ агз)(жГ + Ж2 + X4){X + Хз + Х5){х-\-Щ + хЕ)

The columns represent the clauses; we shall explain shortly why the edges are as they are.

Figure 10.8: Construction of an independent set from a satisfiable boolean expression in 3-CNF

The trick behind the construction of G is to use edges to force any independent set with m nodes to represent a way to satisfy the expression E. There are two key ideas.

1. We want to make sure that only one node corresponding to a given clause can be chosen. We do so by putting edges between all pairs of nodes in a column, i.e., we create the edges ([г, 1], [г, 2]), ([г, 1], [i,3]), and ([г,2], [г,3]), for all i, as in Fig. 10.8.

2. We must prevent nodes from being chosen for the independent set if they represent literals that are complementary. Thus, if there are two nodes [b ,h] and [i2,J2], snch that one of them represents a variable x, and the other represents x, we place an edge between these two nodes. Thus, it is not possible to choose both of these nodes for an independent set.