Are Yes-No Problems Easier?

We might worry that a yes/no version of a problem is easier than the optimization version. For instance, it might be hard to iind a largest independent set, but given a small bound k, it might be easy to verify that there is an independent set of size k. While true, it is also the case that we might be given a constant к that is exactly largest size for which an independent set exists. If so, then solving the yes/no version requires us to find a maximal independent set.

In fact, for all the common problems that are NP-complete, their yes/no versions and optimization versions are equivalent in complexity, at least to within a polynomial. Typically, as in the case of IS, if we had a polynomial-time algorithm to find maximal independent sets, then we could solve the yes/no problem by finding a maximal independent set, and seeing if it was at least as large as the limit k. Since we shall show the yes/no version is NP-complete, the optimization version must be intractable as well.

The comparison can also be made the other way. Suppose we had a polynomial-time algorithm for the yes/no problem IS. If the graph has n nodes, the size of the maximal independent set is between 1 and n. By running IS with all bounds between 1 and n, we can surely find the size of a maximal independent set (although not necessarily the set itself) in n times the amount of time it takes to solve IS once. In fact, by using binary search, we need only a log2 n factor in the runrung time.

The bound к for the graph G constructed by these two rules is m.

It is not hard to see how graph G and bound к can be constructed from expression E in time that is proportional to the square of the length of E, so the conversion oi E to G is a. polynomial-time reduction. We must show that it correctly reduces 3SAT to IS. That is:

£ is satisfiable if and only if G has an independent set of size m.

(If) First, observe that an independent set may not include two nodes from the same clause, [iji] and [i,J2] for some ji ф j- The reason is that there are edges between each pair of such nodes, as we observe from the coliunns in Fig. 10.8. Thus, if there is an independent set of size m, this set must include exactly one node from each clause.

Moreover, the independent set may not include nodes that correspond to both a variable x and its negation x. The reason is that all pairs of such nodes also have an edge between them. Thus, the independent set I of size m yields a satisfying truth assignment T for E as follows. If a node corresponding to a rariable x is in /, then make T{x) = 1; if a node corresponding to a negated

variables is in I, then choose T{x) = 0. If there is no node in / that corresponds to either x or ж, then pick T(x} arbitrarily. Note that item (2) above explains why there cannot be a contradiction, with nodes corresponding to both x and X in /.

We claim that T satisfies E. The reason is that each clause of E has the node corresponding to one of its literals in /, and T is chosen so that literal is made true by T. Thus, when an independent set of size m exists, E is satisfiable.

(Only-if) Now suppose E is satisfied by some truth assignment, say T. Since T makes each clause of E true, we can identify one literal from each clause that T makes true. For some clauses, we may have a choice of two or three of the literals, and if so, pick one of them arbitrarily. Construct a set of m nodes / by picking the node corresponding to the selected literal from each clause.

We claim / is an independent set. The edges between nodes that come from the same clause (the columns in Fig. 10.8) cannot have both ends in /, because we pick only one node from each clause. An edge connecting a variable and its negation cannot have both ends in /, because we selected for / only nodes that correspond to literals made true by the truth assignment T. Of course T will make one of x and x true, but never both. We conclude that if E is satisfiable, then G has an independent set of size m.

Thus, there is a polynomial time reduction from 3SAT to IS. Since 3SAT is known to be NP-complete, so is IS by Theorem 10.5. □

Example 10.19; Let us see how the construction of Theorem 10.18 works for the case where

E- {Xi 4-3=2 + Хз){х{ + X2 + X4){x + Хз + Х){Щ + Щ + x)

We ahready saw the graph obtained from this expression in Fig. 10.8. The nodes are in four columns corresponding to the four clauses. We have shown for each node not only its name (a pair of integers), but the literal to which it corresponds. Notice how there are edges between each pair of nodes ui a column, which corresponds to the literals of one clause. There are also edges between each pair of nodes that corresponds to a variable and its complement. For instance, the node [3,1], which corresponds to x, has edges to the two nodes, [1,2] and [2,2], each of which corresponds to an occurrence of la-

We have selected, by boldface outline, a set I of four nodes, one from each column. These evidently form an independent set. Since their four literals are Xi,X2, X2, and xJ, we can construct from them a truth assignment T that has T(xi) = 1, T(x2) = 1, Т{хз) = 1, and T(x4) = 0. There must also be an assignment for Ж5, but we may pick that arbitrarily, say (2:5) = 0. Now T satisfies E, and the set of nodes I indicates a literal from each clause that is made true by T. □

What are Independent Sets Good For?

It is not the purpose of this book to cover applications of the problems we prove NP-complete. However, the selection of problems in Section 10.4 was taken from a fundamental paper on NP-completeness by R. Karp, where he examined the most important problems from the held of Operations Research and showed a good number of them to be NP-complete. Thus, there is ample evidence available of real problems that are solved using these abstract problems.

As an example, we could use a good algorithm for finding large independent sets to schedule final exams. Let the nodes of the graph be the classes, and place an edge between two nodes if one or more students are taking both those classes, and therefore their finals could not be scheduled for the same time. If we find a maximal independent set, then wc can schedule all those classes for finals at the same time, sure that no student will have a conflict.

10.4.3 The Node-Cover Problem

Another important class of combinatorial optimization problems involves covering of a graph. For instance, an edge covering is a set of edges such that every node in the graph is an end of at least one edge in the set. An edge covering is minimal if it has as few edges as any edge covering for the same graph. The problem of deciding whether a graph has an edge covering with к edges is NP-complete, although we shall not prove it here.

We shall prove NP-complete the problem of node covering. A node cover of a graph is a set of nodes such that each edge has at least one of its ends at a node of the set. A node cover is minimal if it has as few nodes as any node cover for the given graph.

Node covers and independent sets are closely related. In fact, the complement of an independent set is a node cover, and vice-versa. Thus, if we state the yes/no version of the node-cover problem (NC) properly, a reduction from IS is very simple.

PROBLEM: The Node-Cover Problem (NC).

INPUT: A graph G and an upper limit k, which must be between 0 and one less than the number of nodes of G.

OUTPUT: Yes if and only if G has a node cover with к or fewer nodes. REDUCTION FROM: Independent Set.

Theorem 10.20: The node-cover problem is NP-complete,