Computers and Intractability

Last updated
Computers and Intractability: A Guide to the Theory of NP-Completeness
Garey, Johnson, Intractability, cover.jpg
Author Michael R. Garey and David S. Johnson
CountryUnited States
LanguageEnglish
SeriesA Series of Books in the Mathematical Sciences
Subject Computer science
Genre Textbook
Publisher W. H. Freeman and Company
Publication date
1979
Media typePrint
Pagesx+338
ISBN 0-7167-1045-5
OCLC 247570676
519.4
LC Class QA76.6 .G35

Computers and Intractability: A Guide to the Theory of NP-Completeness is a textbook by Michael Garey and David S. Johnson. [1] It was the first book exclusively on the theory of NP-completeness and computational intractability. [2] The book features an appendix providing a thorough compendium of NP-complete problems (which was updated in later printings of the book). The book is now outdated in some respects as it does not cover more recent development such as the PCP theorem. It is nevertheless still in print and is regarded as a classic: in a 2006 study, the CiteSeer search engine listed the book as the most cited reference in computer science literature. [3]

Contents

Open problems

Another appendix of the book featured problems for which it was not known whether they were NP-complete or in P (or neither). The problems (with their original names) are:

  1. Graph isomorphism
    This problem is known to be in NP, but it is unknown if it is NP-complete.
  2. Subgraph homeomorphism (for a fixed graph H)
  3. Graph genus
  4. Chordal graph completion
  5. Chromatic index [4]
  6. Spanning tree parity problem [5]
  7. Partial order dimension
  8. Precedence constrained 3-processor scheduling
    This problem was still open as of 2016. [6]
  9. Linear programming
  10. Total unimodularity [7]
  11. Composite number
    Testing for compositeness is known to be in P, but the complexity of the closely related integer factorization problem remains open.
  12. Minimum length triangulation [8]
    Problem 12 is known to be NP-hard, but it is unknown if it is in NP.

Reception

Soon after it appeared, the book received positive reviews by reputed researchers in the area of theoretical computer science.

In his review, Ronald V. Book recommends the book to "anyone who wishes to learn about the subject of NP-completeness", and he explicitly mentions the "extremely useful" appendix with over 300 NP-hard computational problems. He concludes: "Computer science needs more books like this one." [9]

Harry R. Lewis praises the mathematical prose of the authors: "Garey and Johnson's book is a thorough, clear, and practical exposition of NP-completeness. In many respects it is hard to imagine a better treatment of the subject." Also, he considers the appendix as "unique" and "as a starting point in attempts to show new problems to be NP-complete". [10]

Twenty-three years after the book appeared, Lance Fortnow, editor-in-chief of the scientific journal Transactions on Computational Theory, states: "I consider Garey and Johnson the single most important book on my office bookshelf. Every computer scientist should have this book on their shelves as well. [...] Garey and Johnson has the best introduction to computational complexity I have ever seen." [11]

See also

Related Research Articles

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">Graph isomorphism</span> Bijection between the vertex set of two graphs

In graph theory, an isomorphism of graphsG and H is a bijection between the vertex sets of G and H

<span class="mw-page-title-main">Vertex cover</span> Subset of a graphs vertices, including at least one endpoint of every edge

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

In computational complexity theory, L is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space. Formally, the Turing machine has two tapes, one of which encodes the input and can only be read, whereas the other tape has logarithmic size but can be read as well as written. Logarithmic space is sufficient to hold a constant number of pointers into the input and a logarithmic number of boolean flags, and many basic logspace algorithms use the memory in this way.

Michael Randolph Garey is a computer science researcher, and co-author of Computers and Intractability: A Guide to the Theory of NP-completeness. He and Johnson received the 1979 Frederick W. Lanchester Prize from the Operations Research Society of America for the book. Garey earned his PhD in computer science in 1970 from the University of Wisconsin–Madison. He was employed by AT&T Bell Laboratories in the Mathematical Sciences Research Center from 1970 until his retirement in 1999. For his last 11 years with the organization, he served as its director. His technical specialties included discrete algorithms and computational complexity, approximation algorithms, scheduling theory, and graph theory. From 1978 until 1981 he served as Editor-in-Chief of the Journal of the Association for Computing Machinery. In 1995, Garey was inducted as a Fellow of the Association for Computing Machinery.

In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles. Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest feedback vertex set. The minimum feedback vertex set problem is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.

In graph theory, a degree-constrained spanning tree is a spanning tree where the maximum vertex degree is limited to a certain constant k. The degree-constrained spanning tree problem is to determine whether a particular graph has such a spanning tree for a particular k.

In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.

In computational complexity theory, a gadget is a subset of a problem instance that simulates the behavior of one of the fundamental units of a different computational problem. Gadgets are typically used to construct reductions from one computational problem to another, as part of proofs of NP-completeness or other types of computational hardness. The component design technique is a method for constructing reductions by using gadgets.

In computer science, PPAD is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument. The class attracted significant attention in the field of algorithmic game theory because it contains the problem of computing a Nash equilibrium: this problem was shown to be complete for PPAD by Daskalakis, Goldberg and Papadimitriou with at least 3 players and later extended by Chen and Deng to 2 players.

In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum k for which a clique cover exists is called the clique cover number of the given graph.

In computational complexity theory, the set splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. Set Splitting is one of Garey & Johnson's classical NP-complete problems. The problem is sometimes called hypergraph 2-colorability.

<span class="mw-page-title-main">NP-completeness</span> Complexity class

In computational complexity theory, a problem is NP-complete when:

  1. it is a problem for which the correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
  2. the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

In mathematics, the minimum k-cut, is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to at least k connected components. These edges are referred to as k-cut. The goal is to find the minimum-weight k-cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing.

In graph theory, a branch of mathematics, a chordal completion of a given undirected graph G is a chordal graph, on the same vertex set, that has G as a subgraph. A minimal chordal completion is a chordal completion such that any graph formed by removing an edge would no longer be a chordal completion. A minimum chordal completion is a chordal completion with as few edges as possible.

References

  1. Garey, M. R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp.  x+338. ISBN   0-7167-1045-5. MR   0519066.
  2. Juris Hartmanis (1982). "Computers and Intractability: A Guide to the Theory of NP-Completeness, book review". SIAM Review. 24 (1): 90–91. doi:10.1137/1024022. JSTOR   2029450.
  3. "Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity)" . Retrieved 2007-11-03.
  4. NP-complete: Holyer, Ian (November 1981). "The NP-Completeness of Edge-Coloring". SIAM Journal on Computing. 10 (4): 718–720. doi:10.1137/0210055.
  5. In P: Lovász, L. Lovász, L.; Sós, V.T. (eds.). Algebraic Methods in Graph Theory, Volume II (Colloquium Szeged, 1978). Colloquia Mathematica Societatis János Bolyai, 25. North-Holland. pp. 495–517.
  6. van Bevern, René; Bredereck, Robert; Bulteau, Laurent; Komusiewicz, Christian; Talmon, Nimrod; Woeginger, Gerhard J. (2016). "Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width". DOOR 2016: Discrete Optimization and Operations Research. Lecture Notes in Computer Science. Vol. 9869. Springer-Verlag. pp. 105–120. arXiv: 1605.00901 . doi:10.1007/978-3-319-44914-2_9.
  7. In P: Seymour, P. D. (June 1980). "Decomposition of regular matroids" (PDF). Journal of Combinatorial Theory, Series B. 28 (3): 305–359. doi: 10.1016/0095-8956(80)90075-1 .
  8. Is NP-hard: Mulzer, Wolfgang; Rote, Günter (2008), "Minimum-weight triangulation is NP-hard", Journal of the ACM , 55 (2), Art. 11, arXiv: cs.CG/0601002 , doi:10.1145/1346330.1346336, MR   2417038
  9. Ronald V. Book. Review: Computers and intractability: A guide to the theory of NP-completeness Bull. Amer. Math. Soc. (N.S.), 3(2), pp. 898904, 1980
  10. Harry R. Lewis, Review: Computers and intractability: A guide to the theory of NP-completeness, Journal of Symbolic Logic , Vol. 48(2), pp. 498500, 1983
  11. Lance Fortnow, Great Books: Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson. Computational complexity blog, August 30, 2002.