Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
From MaRDI portal
Publication:4376161
DOI10.1137/S0097539792229507zbMath0884.05071OpenAlexW1964448775WikidataQ123215741 ScholiaQ123215741MaRDI QIDQ4376161
Publication date: 10 February 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539792229507
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (64)
The real truth about star designs ⋮ FORK-DECOMPOSITION OF DIRECT PRODUCT OF GRAPHS ⋮ A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs ⋮ Traffic grooming on the path ⋮ Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial ⋮ Path decompositions of regular graphs with prescribed girth ⋮ Decompositions of highly connected graphs into paths of any given length ⋮ Decompositions of highly connected graphs into paths of length five ⋮ Minimum \(H\)-decompositions of graphs ⋮ Turán function and \(H\)-decomposition problem for gem graphs ⋮ Monochromatic Clique Decompositions of Graphs ⋮ P4-Decomposition of Total Graphs ⋮ Packing seagulls ⋮ Decomposing highly edge-connected graphs into paths of any given length ⋮ Induced star partition of graphs ⋮ Integer and fractional packings of hypergraphs ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Packing 1-plane Hamiltonian cycles in complete geometric graphs ⋮ Computer search for graceful labeling: a survey ⋮ Fractional clique decompositions of dense graphs and hypergraphs ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Edge decompositions and rooted packings of graphs ⋮ Packing 3-vertex paths in claw-free graphs and related topics ⋮ Decomposing subcubic graphs into claws, paths or triangles ⋮ Constructive Packings of Triple Systems ⋮ Edge-decomposition of graphs into copies of a tree with four edges ⋮ A cube dismantling problem related to bootstrap percolation ⋮ The weak 3-flow conjecture and the weak circular flow conjecture ⋮ Star covers and star partitions of double-split graphs ⋮ Smaller embeddings of partial \(k\)-star decompositions ⋮ Towards a solution of the Holyer's problem ⋮ Perfectly packing graphs with bounded degeneracy and many leaves ⋮ Decomposing Semi-complete Multigraphs and Directed Graphs into Paths of Length Two ⋮ Minimalist designs ⋮ Unnamed Item ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ Decomposing graphs into paths of fixed length ⋮ Optimizing regenerator cost in traffic grooming ⋮ Edge-decompositions of graphs with high minimum degree ⋮ On the complexity of deciding whether the regular number is at most two ⋮ A proof of the Barát-Thomassen conjecture ⋮ Decomposing highly connected graphs into paths of length five ⋮ Algorithmic complexity of weakly semiregular partitioning and the representation number ⋮ Monochromatic Kr‐Decompositions of Graphs ⋮ On Rooted Packings, Decompositions, and Factors of Graphs ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ Decomposing dense bipartite graphs into 4-cycles ⋮ Multigraph decomposition into stars and into multistars ⋮ How to allocate review tasks for robust ranking ⋮ Decompositions of highly connected graphs into paths of length 3 ⋮ Decomposing Cubic Graphs into Connected Subgraphs of Size Three ⋮ Polynomial cases of graph decomposition: A complete solution of Holyer's problem ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps ⋮ Edge-decompositions of highly connected graphs into paths ⋮ On some multigraph decomposition problems and their computational complexity ⋮ PARTITIONS OF COMPLETE BIPARTITE GEOMETRIC GRAPHS INTO PLANE PERFECT MATCHINGS ⋮ Packing degenerate graphs ⋮ The Existence and Construction of (K5∖e)-Designs of Orders 27, 135, 162, and 216 ⋮ Covering the edges of bipartite graphs using \(K_{2,2}\) graphs ⋮ Spanning cubic graph designs ⋮ Edge decompositions into two kinds of graphs ⋮ Packing plane spanning graphs with short edges in complete geometric graphs ⋮ Star decomposition of graphs ⋮ Decomposing Graphs of High Minimum Degree into 4‐Cycles
This page was built for publication: Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
