1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 69
Текст из файла (страница 69)
Further, suppose that G has a Hamilton cycle, a cycle whichtraverses each node of G exactly once. The question is, via which edges is theHamilton cycle going to traverse the three middle nodes? It is easy to see thatthere are really only two possibilities: Either the edges (a, u), (n, v), (v, w), (10, b)are a part of the Hamilton cycle, or the edges (c, w), (w, v), (v, u), (u, d) are. Allother possibilities leave some of the three nodes untraversed by the Hamiltoncycle, which therefore is not Hamilton at all.To put it otherwise, this simple device can be thought of as two edges (a, b)and (c, d) with the following additional constraint: In any Hamilton cycle ofthe overall graph G, either (a, b) is traversed, or (c, d) is, bl1,t not both.
Thissituation can be depicted as in Figure 7-5(b), where the two otherwise unrelatededges are connected by an exclusive or sign, meaning that exactly one of them isto be traversed by any Hamilton cycle. Whenever we show this construct in ourdepiction of a graph, we know that in fact the graph contains the full subgraphshown in Figure 7-5(a). In fact, we can have several edges connected by suchsubgraphs with the same edge (see Figure 7-5(c)).
The result is the same: Eitherall edges on one side are traversed, or the edge on the other, but not both.a3217.3: More NP-complete Problemsbaa.~------~-------cdc(b)(a)••••(c)Figure 7-5This device is central to our construction of the graph G = T(U, F), corresponding to the instance of EXACT COVER with U = {Ul ... ,Un} and F ={S] , ...
,Sm}' We describe the graph G next. There are nodes Uo, Ul, ... ,Un andSo, SI, ... ,Sm, that is, one for each element of the universe, and one for eachset in the given instance, plus two more nodes. For i = 1, ... ,m, there are twoedges (Si-l, Si). Of course, in graphs it makes no sense to have two differentedges connecting the same pair of nodes. The only reason we allow it in thepresent case is that the edges will be later joined by "exclusive or" subgraphsas in Figure 7-4, and thus there will be no "parallel" edges at the end of theconstruction.
One of the two edges (Si-l, Si) is called the long edge, and theother is the .short edge. For j = 1, ... ,n, between the nodes Uj-l and Uj thereare a.s many edge.s a.s there are .set.s in F containing the element Uj. This way,we can think that each copy of the edge (Uj -1, U j) corresponds to an appearanceof Uj in a set. Finally, we add the edges (un, So) and (Sm, uo), thus "closing thecycle."Notice that the construction so far only depends on the size of the universeand the number and sizes of the sets; it does not depend on preci.sely which322Chapter 7: NP-COMPLETENESSFigure 7-6sets contain each element. This fine structure of the instance will influenceour construction as follows: As each copy of edge (Uj -1 , Uj) corresponds to anappearance of element Uj in some set 5 i E F such that Uj E 5 i , we join by an"exclusive or" subgraph this copy of edge (Uj-1, Uj) with the long edge (5i - 1 , 5 i )(see Figure 7-6 for an illustration).
This completes the construction of the graphT(U, F).We claim that the graph T(U, F) has a Hamilton cycle if and only if T(U, F)has an exact cover. First, suppose that a Hamilton cycle exists. It must traversethe nodes corresponding to the sets in the order 5 0 ,5], ... , 5 m , then traversethe edge (5m , uo), then the nodes uo, U1, ... , Un, and finally finish along the edge(u n ,50 ) (see Figure 7-6). The question is, will it traverse for each set 5 j theshort or the long edge (5 j - 1 , 5 j )? Let C be the set of all sets T j such that theshort edge (5 j - 1 , 5 j ) is traversed by the Hamilton cycle.
We shall show that C isa legitimate set cover; that is, it contains all elements without overlaps. But thisis not hard to see: By the property of the "exclusive or" subgraph, the elementsin the sets in C are precisely the copies of edges of the form (Ui-1, Ui) that are7.3: More NP-complete Problems323traversed by the Hamilton cycle; and the Hamilton cycle traverses exactly onesuch edge for each element Uj E U. It follows that each Uj E U is contained inexactly one set in C, and thus C is an exact cover.Conversely, suppose that an exact cover C exists. Then a Hamilton cyclein the graph T(U,:1") can be constructed as follows: Traverse the short copies ofall edges (Sj-l,Sj) where Sj E C, and the long edges for all other sets.
Thenfor each element Ui, traverse the copy of the edge (Ui-l, Ui) that corresponds tothe unique set in C that contains Ui. Complete the Hamilton cycle by the edges(Un' So) and (Sm,UO) .•Once a problem is shown to be NP-complete, research often is focused onsolving interesting yet tractable special cases of the problem. NP-completenessproofs often produce instances of the target problem that are complex and "unnatural." The question often persists, whether the instances that are of interestin practice, being much less complex, may not be solvable by some efficient algorithm.
Alternatively, it can be often shown that even substantially restrictedversions of the problem remain NP-complete. We have already seen both patterns in connection to SATISFIABILITY, whose special case 2-SATISFIABILITY canbe solved in polynomial time, whereas the special case 3-SATISFIABILITY is Npcomplete. To introduce an interesting special case of HAMILTON CYCLE, defineUNDIRECTED HAMILTON CYCLE to be the HAMILTON CYCLE problem restrictedto graphs that are undirected, that is, symmetric without self-loops.Theorem 7.3.3: UNDIRECTED HAMILTON CYCLE is NP-complete.Proof: We shall reduce the ordinary HAMILTON CYCLE problem to it. Given agraph G <;;;; V x V, we shall construct a symmetric graph G' <;;;; V' X V', withoutself-loops, such that G has a Hamilton cycle if and only if G ' has one. Theconstruction, illustrated in Figure 7-7, is this: First, V' = {VO,Vl,V2: v E V},that is, G' has three nodes va, VI, and V2 for each node v of G. Of these va is,informally, the entry node, to which edges coming into v will be directed, andV2 is the exit node, from which edges going out of v will emanate.Figure 7-7Thus, the edges in G' are these (see Figure 7-7; recall that undirected graphsare more conveniently depicted by undirected lines connecting the nodes):{(U2'va), (va, U2) : (u, v) E G} U {(va, vr), (VI, va), (VI, V2),(V2,vI) : v E V)}.324Chapter 7: NP-COMPLETENESSThat is, the nodes vo, VI, V2 are connected by a path in this order, and there isan undirected edge between U2 and Vo whenever (u, v) E G.
This completes theconstruction of G'.We must now prove that G' has a Hamilton cycle if and only if G has one.Suppose that a Hamilton cycle of G' arrives at node Vo from an edge of the form(U2, vo). If the Hamilton cycle leaves Vo through an edge other than (Vo, VI ),then it cannot "pick up" node VI in any other way, and thus it was erroneouslyassumed to be a Hamilton cycle. Thus, edge (VO,Vl) must be a part of thecycle, and so is (Vt, V2). Then the cycle must continue through one of the edges(V2,1[10), where (v,w) E G, from there to WI, W2, to some zo where (w,z) E G,and so on.
Therefore, the edges of the form (uo, V2) in the Hamilton cycle ofG' constitute in fact a Hamilton cycle of G. Conversely, any Hamilton cycle(VI, v 2 , ••• , vlVl) of G can be converted into a Hamilton cycle of G' as follows:1 , VI'1 V2,1 V2 , VI'2 V2 , ... , VoIVI , VIIVI , V IVI) . HI(voHe concI u d e t h at G h as a H·lamI ton22ocycle if and only if G' has a Hamilton cycle, and the proof is complete .•Our next result concerns the notorious TRAVELING SALESMAN PROBLEM-its "yes-no" version, in which each instance is supplied with a budget B, asdefined in Section 6.2.Theorem 7.3.4: The TRAVELING SALESMAN PROBLEM is NP-complete.Np. To show completeness,we shall reduce UNDIRECTED HAMILTON CYCLE to the TRAVELING SALESMANPROBLEM.
Given a symmetric graph G, where without loss of generality V ={VI, ... , VIVI}, we construct the following instance of the TRAVELING SALESMANPROBLEM: n, the number of cities, is lVI, and the distance d ij between any twocities i and j is0 if i = j;d ij = { 21 if (Vi, Vj) E G;otherwise.Since G is a symmetric graph without loops, this distance function is itselfsymmetric; that is to say, dij = d ji for all cities i and j, as required. Finally,the budget is B = n.Obviously, any "tour" of the cities has cost equal to the number of n plusthe number of the intercity distances traversed that are not edges of G. Thus,a tour of cost B or less exists if and only if the number of "nonedges" used iszero, that is, if and only if the tour is a Hamilton cycle of G .
•Proof: We already know that the problem is inPartitions and CliquesEXACT COVER also provides a nice proof of the NP-completeness of PARTITION.It is easiest to start from the closely related KNAPSACK problem, in which anarbitrary sum K to be achieved is given (recall its definition in Example 7.1.2):3257.3: More NP-complete ProblemsTheorem 7.3.5: KNAPSACK is NP-complete./lfp is clear: Given an instance of KNAPSACKand K, a subset P of {I, ... ,n} such that L:iEP ai = K can serve asa eertificate that the answer to the given instance is "yes." It is polynomiallysuccinct, and it can be tested in polynomial time by binary addition.We shall now reduce EXACT COVER to KNAPSACK. We are given a universeU = {U1 ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
