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

Pages cited

94-102

ISBN

9780716710448

Link

https://archive.org/details/computersintract0000gare

Cited from

cognitive_science, mathematics, operations_research

Cited by

12 citations across 12 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.

• Monochromatic triangle
  • The two-color version asks whether edges can be partitioned into two triangle-free subgraphs, is NP-complete in general and becomes tractable under bounded structural parameters such as treewidth.
• Nondeterministic Turing machine
  • Nondeterminism does not expand computable languages over deterministic Turing machines, but polynomial-time simulation cost motivates NP and complexity questions; branch and halting conventions must be stated.
• 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..
• Set splitting problem
  • The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Verification

Does it exist? Confirmed. This work's ISBN resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Not recorded. Neither this nor any other of the 12 citations of this work carries a recorded support check.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

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