Computers and Intractability

Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness.

Type

Book

Intellectual base

Review or monograph

Year

1979

ISBN

9780716710448

Link

https://archive.org/details/computersintract0000gare

Cited from

cognitive_science, mathematics, operations_research

Cited by

9 citations across 9 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Embeddability
  • Two placements that look alike can differ entirely in whether they embed because the conflict predicate is subtly different: planar graph embedding allows edges to share endpoints, while graph 3-colouring asks about adjacency-not-same-colour — the same graph under different predicates yields different answers.

    This sourceStandard reference for the NP-hardness of graph coloring, bin packing, and related embedding/feasibility problems, and for polynomial special cases under structural restriction.

• Graph Coloring
  • The general coloring problem is NP-hard, but planar graphs are four-colorable in polynomial time, interval and bipartite graphs in linear time, and chordal graphs by simplicial elimination.

    This sourceEstablishes graph coloring as NP-complete in general while restricted classes (planar, bipartite, interval, chordal) admit polynomial or linear exact algorithms.

• Problem Space
  • Structural tension: Many problem spaces grow exponentially with problem size, a regime Garey and Johnson (1979) characterize as the gap between formal completeness and practical intractability.

    This sourceW. H. Freeman. Canonical reference on combinatorial complexity: catalogs problems whose state spaces grow exponentially with input size and formalizes the gap between formal completeness of search algorithms and their practical intractability.

• Scheduling
  • Not always optimal: many scheduling problems are NP-hard (Garey and Johnson (1979) showed that job-shop with more than 2 machines, flow- shop with more than 2 machines, and most parallel-machine problems with precedence constraints are NP-complete or NP-hard in the strong sense).

    This sourceW. H. Freeman. Canonical reference on combinatorial complexity: catalogs problems whose state spaces grow exponentially with input size and formalizes the gap between formal completeness of search algorithms and their practical intractability.

• Verifier-Prover Asymmetry
  • The finding cost from scratch — locating a satisfying assignment — is, for the general case, believed to require time that grows exponentially in \(n\): no algorithm is known that beats brute search by more than constant or polynomial factors, and the conjecture P \(\neq\) NP says none exists.

    This sourceThe exponential-find/polynomial-verify gap for SAT and the conjecture P != NP.

Domain-specific

• Domatic number
  • … For a complete graph \(K_n\), the \(n\) singleton vertex blocks each dominate the graph, so \(d(K_n)=n\). to If \(G\) has minimum degree \(\delta\), then \(d(G)\leq\delta+1\), because every dominating block must contain a vertex from the closed neighborhood of a minimum-degree vertex. demonstrates that continuity.
• Minimum Relevant Variables in a Linear System
  • Garey and Johnson included the associated NP-hard problem in their catalog; Amaldi and Kann systematically analyzed equality and inequality/non-equality variants and approximation hardness.

    This sourceCanonical source for the minimum-weight solution-to-linear-equations hardness problem.

• Pseudo-polynomial transformation
  • Additional size inequalities prevent the map from hiding an exponential blow-up or mapping polynomially bounded source instances to numerically unbounded target instances.

    This sourceW. H. Freeman. ISBN 978-0-7167-1045-5.

• Reduction (complexity)
  • … a convenient observable transfers from A polynomial-time mapping from SAT instances to vertex-cover instances proves vertex cover at least as hard as SAT under that reduction. to A proof gives both directions of answer preservation and includes transformation cost rather than citing superficial encoding similarity..

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:5d1160d4a9df · see in the full table