Computers And Intractability A Guide To The Theory Of Np Completeness－PDF

Computers And Intractability A Guide To The Theory Of Np Completeness. PDF版CONTENTSONTENTS4 Using NP- Complete ness to analy ze ProblemsA5 Sequencing and Scheduling.2364. 1 Analyzing SubproblemsOne p:4.2 Number Problems and Strong NP-CompletenessA5.2 Multiprocessor Scheduling,,.2384.2.1 Some additional definitionsAS 3 Shop Schedul4.2.2 Proving Slrong NP-Completeness Results...... 95A5.4 Miscella2434.3 TIme Complexity as a Function of Natural Parameters ,., 106A6 Mathematical ProgrammingA? Algebra and Number TheoryA7. 1 Divisi bility Proble2495 NP-hardness109A7.2 Solvability of quations2505.1 Turing reducibility and nP-hard ProblcmsA7, 3 Miscellaneous2545.2 A Terminological History...118A8 Games and puzzlesA9 LogicA9. 1 Propositional Logic6 Coping with NP-Complete ProblemsA9.2 Miscellaneous6.1 Performance Guarantees for Approximation AlgorithmsAl0 Automata and Language Theory2656.2 Applying NP-Completeness to Approximation Problems .. 13A10.1 Automata Theory6.3 Performance Guarantees and Behavior "In Practice148Al0. 2 Formal LanguagesAll Program Opt imizationAll1 Code Generation7 Beyond NP-Completeness,,153All 2 Programs and Schemes2757.1 The Structure of NPAl2 MiscellanousAl3 Open Problems2857.2 The Polynomial Hierarchy7. 3 The Complexity of Enumeration Problems1677.4 Polynomial Space Completeness170Symbol index ..........2897.5L7.6 Proofs of Intractability and P vs. NP18]Reference and Author Index291Appendix: A List of NP-Colmplete Problems187Subject index……,…………,…327Al Graph Theoryovering and PartitioningUpdate for the Current Printing….……..…339Al. 2 Subgraphs and Supergraphs19A1, 3 Vertex OrderingAl.4 Iso-and Other morphismsA1. 5 MiscellaneousA2 Network Design206A2. 1 spanning Trees206A2. 2 Cuts and Connectivity209A2.3 Routing ProblemsA2.4 Flow Problems4A2. 5 Miscellaneous218A3 Sets and Partitio221A3. 1 Covering, Hitting, and Splitting221A3.2 Weighted Set Problemsa4 Storage and retrievalA. Data Storage226A42 Compression and represen tation,,228A43 Database problems232refaceFew technical terms have gained such rapid notoriety as thelaLion NP-complete. In the short time since its introduction in the early1970s, this term has come to symbolize the abyss of in herent intractabilitythat algorithm designers increasingly face as they seek to solve larger andmore complex problems. A wide variety of commonly encountered problems from mat hemalics, computer science and operations research are nowbe NP-complete, and the collgrow almos: daily. Indeed, the NP-complete problems are now so pervasivethat it is important for anyone concerned with the computational aspects olI hese fields to be familiar with the meaning and implications of this conceptThis book is intended as a detailed guide to the theory of NPcompleteness, emphasizing those concepts and techniques that seem to bemost useful for applying the thcory to practical problems. It can be viewedas consisting of three partsThe tirst part, Chapters I through 5, covers the basic theory of NPcompleteness. Chapter 1 presents a relatively low-level introduct ion tosome of the central notions of computational complexity and discusses thesignificance of NP-completeness in this context. Chapters 2 through 5 pro-vide the detailed definitions and proof techniques necessary for thoroughlyunderstanding and applying the theoryThe second parL, Chapters 6 and 7, provides an overview of two alternalive directions for further study. Chapter 6 concentrates on the searchfor effcient'approximation algorithms for NP-compl ete problems, an areawhose de velopment has seen considerable interplay with the theory of NPcompleteness. Chapter 7 surveys a large number of theoretical topicscomputational complexity, many of which have arisen as a consequence ofprevious work on NP-completeness. Both of these chapters ( especiallyChapter 7)are intended solely as introductions to thesc arcas, with our cxpectation being that any reader wishing to pursue particular topics in moredetail will do so by consulting the cited referencesThe third and final part of the book is the appendix, which containsan extensive list (more than 300 main entries, and several times this manylts in total) of NP-complctc and NP-hard problems. annotatin entries discuss what is kndbout thelexity of subproblemsand variants of the stated problemsPREFACECOMPUTERS AND INTRACTABILITYA Guide to the Theory of NP-CompletenessThe book should be suitable for use as a supplementary text incourses on algorithm design, computational complexity, operations researchor combinatorial mathematics. It also can be used as a starting point forseminars on approximation algorithms or computational complexity at thegraduate or advanced undergraduate level. The second author has used apreliminary draf: as the basis for a graduate seminar on approximation algocovering Chapters 1 through 5 in about five weeks and theing the topics in Chapter 6, supplementing them extensively with additionalmaterial from the references. A seminar on computational complexitymight proceed similarly, substituting Chapter 7 for Chapter 6 as the initialaccess point to the literature. It is also possible to cover both chapters in acombined seminarMore generally, the book can serve both as a self-study text for anyone interested in learning about the subject of nP-completeness and asreference book for researchers and practitioners who are concerned with algorithms and their complexity. The list of NP-complete problems in theAppendix can be used by anyone familiar with the central notions of NPcompleteness, even without having read the material in the main text. Tnovice can gain such familiarity by skimming the material in Chapters Ithrough 5, concentrating on the informal discussions of definitions andtechniques, and returning to the more formal material only as needed forclarification. To aid those using the book as a reference we have included asubstantial number of terms in the Subject Index, and the extensive refer-ence and Author Index gives the sections where each reference is men-tioned in the textWe are indebted to a large number of people who have helped usgreatly in preparing this book. Hal Gabow, Larry Landweber, and Bob Tar-jan taught from preliminary versions of the book and provided us with valuable suggestions based on their experience. The following people read preliminary drafts of all or part of the book and made constructive comments:Al Aho, Shimon Even, Ron Graham, Harry Hunt, Victor Klee, AlbertMeyer, Christos Papadimitriou, Henry Pollak, Sartaj Sahni, Ravi Sethi, Lar-ry Stockmeyer, and Jeff Ullman. A large number of researchers, toonumerous to mention here (but see the Reference and Author Index)responded to our call for NP-completeness resuits and contributed towardmaking our fist of NP-complete problems as extensive as it is. Several ofour colleagues at Bell Laboratories, especially Brian Kernighan, provided in-valuable assistance with computer typesetting on the UNIX@ system. Final-ly, special thanks go to Jeanette reinbold, whose facility with translatiour handwritten hieroglyphics into faultless input to the typesetting systemmade the task of writing this book so much easierMurray Hill, New JerseyMICHAEL R, GAREYOctober. 1978DAVID S. JOHNSONComputers, Complexity,and Intractability1.1 introdThe subject matter of this book is perhaps best introduced through thfollowing, some what whimsical, exampleSuppose thatlike the authors, are employed in the halls of indus.try. One day your boss calls you into his office and confides that the com-pany is about to enter the highly competitive bandersnatch" market. Forthis reason, a good method is needed for determining whether or not anygiven set of specifications for a new bandersnatch component can be metnd, if so, for constructing a design that meets them. Since you are thecompany s chief algorithm designer, your charge is to find an efficient aigo-rithm for doing this.ter consulting with the bandersnatch department to determine exactlywhat the probiem is, you eagerly hurry back to your office pull down yourreference books, and plunge into the task with great enthusiasm. Someweeks iater, your office filled with mountains of crumpled-up scratch paperyour enthusiasm has lessened considerably. So far you have not been ableto come up with any algorithm substantially better than searching throughali possible designs. This would not particularly endear you to your boss,would involve years of computation time for just one setCOMPUTERS, COMPLEXITY, AND INTRACTABILITY1.1 INTRODUCTIONspecifications, and the bandersnatch department is already 13 componentsaimost as good. The theory of NP-completeness provides many straightforbehind schedule. You certainly don t want to return to his office and reward techniques for proving that a given problem is just as hard"as alarge number of other problems that are widely recognized as being dificultand that have been confounding the experts for years. Armed with thesetechniques, you might be able to prove that the bandersnatch problem isNP-complete and, hence, that it is equivalent to all these other hard problems. Then you could march into your boss's ofice and announcec91皇.2I cant find an efficient algorithm, I guess I' m just too dumbTo avoid serious damage to your position within the company, it wouldbe much better if you could prove that the bandersnatch problem is inherenty intractable, that no algorithm could possibly solve it quickly, Youthen could stride confidently into the boss's office and proclaim<'l can t find an efficient algorithm, but neither can all these famous peopleAt the very least, this would inform your boss that it would do no good 10fire you and hire another expert on algorithmsOf course, our own bosses would frown upon our writing this book ifits sole purpose was to protect the jobs of algorithm designers. Indeed, discovering that a problem is NP-complete is usually just the beginning ofwork on that probiem. The needs of the bandersnatch department won'tdisappear overnight simply because their problem is known to be NPcomplete. However, the knowledge that it is NP-complete does providevaluable information about what lincs of approach have the potential of beI cant find an eficient algorithm, because no such algorithm is possible! "ing most productive. Certainly the search for an efficient, exact algorithshould be accorded low priority. It is now more appropriate to concentrateon other, less ambitious, approaches for example you might look forUnfortunately, proving inherent intractability can be just as hard asefficient algorithms that solve various special cases of the general problemfinding efficient algorithms. Even the best theoreticians have been stymiedYou might look for algorithms that, though not guaranteed to run quicklyin their attempts to obtain such proofs for commonly encountered hardseem likely to do so most of the time. Or you might even relax the prob-problcms. However, having read this book, you have discovered somethinglem somewhat, looking for a fast algorithm that merely finds designs thatCOMPUTERS. COMPLEXITY, AND INTRACTABILITY1.2 PROBLEMS. ALGORITHMS AND COMPLEXITYmeet most of the component specifications. In short, the primary applica-tion of the theory of NP-completeness is to assist algorithm designers indirecting their problem-solving efforts toward those approaches that havethe greatest likelihood of leading to uscful algorithmsn the first chapter of this guide"to NP-completeness, we introducemany of the underlying concepts discuss their applicability (as well as givesome cautions ), and outline the remainder of the book31.2 Problems, Algorithms, and ComplexityIn order to elaborate on what is meant by " inherently intractableproblems and problems having equivalent"difficulty, it is important thatwe first agree on the meaning of several more basic termsFigure 1.1 Ar instance of the traveling salesman problem and a tour of length 27.Let us begin with the notion of a problem. For our purposes, a problemwhich is the minimum possible in this case.will be a general question to be answered, usually possessing several param.eters, or free variables, whose values are left unspecified. a problem issalesman problem unless it always constructs an ordering that gives adescribed by giving: (1)a general description of all is parameters, and(2)minimum length tour.a statement of what properties the answer, or solution, is required to satisfyIn general, we are interested in finding the most"eficient"algorithmAn instance of a problcm is obtained by specifying particular values for allfor solving a problem. In its broadest sense the notion of efficiency inthe problem parametersvolves all the various computing resources needed for executing an algo-As an example, consider the classical "traveling salesman problemrithm. However, by the most efficient' algorithm one normally means theThe parameters of this problem consist of a finite set C=ict,c2fastest. Since time requirements are often a dominant factor determiningof " cities"and, for each pair of cities ci, c, in C, t he "distance"'d(owhether or not a particular algorithm is efficient enough to be useful inbetween them. A solution is an ordering is a solution for this instance as the corresponding tour hasput data. If we are to deal with time requirements in a precise, mathematithe minimum possible tour length of 27cal manner, we must take care to define instance sizc in such a way that allAlgorithms are general, step-by-step procedures for solving problemsthese factors are taken into accountFor concreteness, we can think of them simply as being computer programs.To do this, observe that the description of a problem instance that wewritten in some precise computer language An algorithm is said to solveprovide as input to the computer can be viewed as a single finite string ofproblem Ii if that aigorithm can be applied to any instance of I andsymbols chosen from a finite input alphabet. Although there are manyguaranteed always to produce a solution for that instance I We emphasizedifferent ways in which instances of a given problcm might bc described, letthat the term solution"is intended here strictly in the sernse introducedus assume that one particular way has been chosenin advance and that eachabove, so that, in particular, an aigorithm does not 0. A polynompresent machinc. Observe that with the 2n algorithm a thousand-fold in-aI time algorithm is defined to be onc whose time complexity function iscrease in computing speed only adds 10 to the size of the largest problemstance we can solve in an hour, whereas with the algorithm this size al-o(p(n))for some polynomial function P, where n is used to denote the in-put length. Any algorithm whose time complexity function cannot be somost quadruplesbounded is called an exponential time algorithm(although it should be notedThese tables indicate some of the reasons why poly nomial time algo-that this definition includes certain non-polynomial time complexity furithms are generally regarded as being much more desirable than exponentions, like nogm, which ate not normally regarded as exponential functions)tial time algorithms. This view, and the distinction between the two typesof algorithms, is central to our notion of inherent intractability and to theThe distinction between these two types of algorithms has particulartheory of NP-completenesssignificance when considering the solution of large probiem instances. FigThe fundamental nature of this distinction was first discussed in [Cob-ure 1. 2 illustrates the differences in growth rates among several typical complexity functions of each type, where the functions express execution timeham, 1964] and [Edmonds, 1965a]. Edmonds, in particular, cquatcd polyCOMPUTERS, COMPLEXITY, AND INTRACTABILITY1.3 POLY NOMIAL TIME ALGORITHMS AND INTRACTABLE PROBLEMSSize of largest problem Instancethat appears: a hold for several well-known algorithms. The simplex algo-Solvable in 1 Hourrithm for linear programming has been shown to have exponential timecomplexity [Klee and Minty, 1972, [Zadeh, 1973, but it has an impressirecord of running quickly in practicc. Likewise, branch-and-bound algocomplexity I With present With computer With computerrithms for the knapsack problem have been so successful that many consid-functioncomputer100 times faster 1000 times fasterer it to be a well-solvedproblem, even though these algorithms, toohave exponential time complexity100N11000N1Unfortunately, examples like these are quite rare. Although exponential time algorithms are known for many problems, few of them are regardN210N231.6N2ed as bcing very useful in practice. Even the successful exponential time alIs mentioned above have not stopped researchers from continuing to10Nsearch for poly nomial time algorithms for sol ving t hose problems. In factthe verof these algorithms has led to the suspic2.5N43.98Na crucialof the problems whose refinement couldlead to still better methods. So far, little progress has been made towardNs+664Ns+9.97plaining this success, and no methodsfor predicting in adnce that a givential time algorithm will run quickly in prN5+6.29On the ot her hand, the much more stringent bounds on execution timesfied by polynomial1. predictions to beFigure 1.3 Effect of improved technology on several polynomial and exponentialmade. Even though an algorithm ha ving time complexity n 00 or 1099n2time algorithmsmight not be considered likely to run quickly in practice, the polynomiallysolvable problems that arise naturally tend to be solvable within polynomialnomial time algorithms with"good" algorithms and conjectured that certatime bounds that have degree 2 or 3 at worst and that do not involve exnteger programming problems might not be solvable by such good"algo-tremely large coefficients. Algorithms satisfying such bounds can be conithms. This reflects the viewpoint that exponential time algorithms shouldsidered to be provably efficient, " and it is this much-desired property thatnot be considered" algorithms, and indeed this usuaily is the casemakes polynomial time algorithms the preferred way to solve problems.Most exponential time algorithms are merely variations on exhaustOur definition of intractable''also provides a theoretical frame work ofsearch, whereas polynomial time algorithms generally are made possibleconsiderable generality and power. The intractability of a problem turns outonly through the gain of some deeper insight into the structure of a prob-to be essentially independent of the particular encoding scheme and comfem. There is wide agreement that a problem has not been well-solvedputer model used for determining time complexityuntil a polynomial time algorithm is known for it. Hence, we shall refer toa problem as intractable if it is so hard that no polynomial time algorithmcan possibly sol vewhere V is the set of vertices and e is the set of edges, each edge being anOf course, this formal use of "intractable should be viewed only as aunordered pair of vertices. Such an instance might be described(see Figureough approximation to its dictionary meaning. The distinction between1. 4) by simply listing all the vertices and edges or by listing the rows of theefficient polynomial time algorithms and 'inefficient" exponential timedjacency matrix for the graph, or by listing for cach vertex all the otheralgorithms admits of many exceptions when the problem instances of invertices sharing a common edge with it (a"neighbor"list). Each of theseterest have limited size. Even in Figure 1.2, the 2n algorithm is faster thanencodings can give a different input length for the same graph. However, itthe n'algorithm for n 20. More extreme examples can be constructedis easy to verify (see Figure 1.5)that the input lengths they determineeasily.differ at most polynomially from one another, so that any algorithm having&. Furthermore, there are some exponential time algorithms that havepoly nomial time complexity under one of these cncoding schemes also willeen quite useful in practice Time comp lexity as defined is a worst-casehave polynomial time complexity under all the others. In fact, the standardmeasure,and the fact that an algorithm has time complexity 2 means onlyencoding schemes used in practice for any particular problem al ways seemthat at least one problem instance of size n requires that much time. Mostto differ at most polynomially from one another. It would be difficult toproblem instances might actually require far less time than that, a situationimagine a reasonable"encoding scheme for a problem that differs more