Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture

DOI10.1137/S0097539792229507zbMATH Open0884.05071OpenAlexW1964448775WikidataQ123215741 ScholiaQ123215741MaRDI QIDQ4376161FDOQ4376161

Authors: Michael Tarsi, Dorit Dor 

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

Recommendations

• NP-completeness of graph decomposition problems
• Polynomial cases of graph decomposition: A complete solution of Holyer's problem
• On a decomposition of complete graphs
• Decompositions of Complete Graphs
• On the completeness of decomposable properties of graphs
• Decomposing the complete \(r\)-graph
• On decompositions of complete hypergraphs
• scientific article; zbMATH DE number 2197887
• Complete decomposable graphs

zbMATH Keywords

NP-completeness\(H\)-decomposition of a graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (70)

• Optimizing regenerator cost in traffic grooming
• Edge decompositions and rooted packings of graphs
• Spanning cubic graph designs
• Decomposing cubic graphs into connected subgraphs of size three
• Packing 1-plane Hamiltonian cycles in complete geometric graphs
• Inapproximability of \(H\)-transversal/packing
• Combinatorial and computational aspects of graph packing and graph decomposition
• Packing plane spanning graphs with short edges in complete geometric graphs
• Fractional clique decompositions of dense graphs and hypergraphs
• How to allocate review tasks for robust ranking
• Decompositions of highly connected graphs into paths of length 3
• P₄-Decomposition of Total Graphs
• The real truth about star designs
• Towards a solution of the Holyer's problem
• Input-output decomposition of dynamic systems is NP-complete
• Integer and fractional packings of hypergraphs
• Edge-decompositions of graphs with high minimum degree
• Perfectly packing graphs with bounded degeneracy and many leaves
• Decomposing graphs of high minimum degree into 4-cycles
• The weak 3-flow conjecture and the weak circular flow conjecture
• Multigraph decomposition into stars and into multistars
• Turán function and \(H\)-decomposition problem for gem graphs
• Partitions of complete bipartite geometric graphs into plane perfect matchings
• On some multigraph decomposition problems and their computational complexity
• Decomposing dense bipartite graphs into 4-cycles
• On rooted packings, decompositions, and factors of graphs
• Traffic grooming on the path
• Packing 3-vertex paths in claw-free graphs and related topics
• 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
• Star decomposition of graphs
• Decomposing highly edge-connected graphs into paths of any given length
• Edge-decomposition of graphs into copies of a tree with four edges
• Packing seagulls
• Induced star partition of graphs
• Packing degenerate graphs
• On the Weisfeiler-Leman dimension of fractional packing
• Minimum \(H\)-decompositions of graphs
• Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
• Minimalist designs
• Graph decomposition of slim graphs
• A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs
• Edge-decompositions of highly connected graphs into paths
• A cube dismantling problem related to bootstrap percolation
• Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
• Covering the edges of bipartite graphs using \(K_{2,2}\) graphs
• Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
• Constructive Packings of Triple Systems
• Edge decompositions into two kinds of graphs
• Title not available (Why is that?)
• On the complexity of deciding whether the regular number is at most two
• Graph factors and factorization: 1985--2003: a survey
• Decomposing highly connected graphs into paths of length five
• Polynomial cases of graph decomposition: A complete solution of Holyer's problem
• A proof of the Barát-Thomassen conjecture
• Algorithmic complexity of weakly semiregular partitioning and the representation number
• Decomposing graphs into paths of fixed length
• FORK-DECOMPOSITION OF DIRECT PRODUCT OF GRAPHS
• Decomposing semi-complete multigraphs and directed graphs into paths of length two
• Partitioning the edge set of a bipartite graph into the minimal number of subgraphs isomorphic to those of a simple 4 order cycle
• Decomposing subcubic graphs into claws, paths or triangles
• Monochromatic \(K_{r}\)-decompositions of graphs
• The existence and construction of \((K_{5}\setminus e)\)-designs of orders 27, 135, 162, and 216
• Smaller embeddings of partial \(k\)-star decompositions
• Star covers and star partitions of double-split graphs
• On star partition of split graphs
• Star covers and star partitions of cographs and butterfly-free graphs
• Computer search for graceful labeling: a survey
• Monochromatic clique decompositions of graphs

This page was built for publication: Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376161)