NP-completeness of graph decomposition problems
For a fixed graph \(H\), the \(H\)-decomposition problem is as follows: Can a given (input) graph \(G\) be decomposed as an edge disjoint union of subgraphs, all of which are isomorphic to \(H\)? \textit{I. Holyer} [SIAM J. Comput. 10, 797-808 (1981; Zbl 0468.68069)] conjectured that the \(H\)-decomposition problem is \(NP\)-complete whenever \(H\) has at least 3 edges and is connected. Holyer's conjecture had been proved for \(H=K_ m\) (a complete graph), \(P_ m\) (a path) and \(C_ m\) (a cycle). The main result of this paper is: If \(H\) is a connected graph with at least three edges and \(H\) has a vertex \(v\) such that all the vertices adjacent to \(v\), except at most one of them, are of degree one in \(H\), then the \(H\)-decomposition problem is \(NP\)-complete. From this it follows that Holyer's conjecture is true for a family of graphs which includes all trees with at least three edges.
- 3K2-decomposition of a graph
- A note on the decomposition of graphs into isomorphic matchings
- scientific article; zbMATH DE number 3974987 (Why is no real title available?)
- scientific article; zbMATH DE number 3710196 (Why is no real title available?)
- scientific article; zbMATH DE number 3517174 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- On the completeness of a generalized matching problem
- The NP-Completeness of Some Edge-Partition Problems
- Mutual exclusion scheduling with interval graphs or related classes. I
- Polynomial cases of graph decomposition: A complete solution of Holyer's problem
- Edge decompositions into two kinds of graphs
- Decomposition of large combinatorial structures
- A Helly property of arcs
- Trahtenbrot-Zykov problem and NP-completeness
- Graph decomposition of slim graphs
- Edge-disjoint packings of graphs
- Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
- Delta-system decompositions of graphs
- The mutual exclusion scheduling problem for permutation and comparability graphs.
- Clique and anticlique partitions of graphs
- Algorithmic problems in right-angled Artin groups: complexity and applications
- Scheduling jobs on identical machines with agreement graph
- Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
- On some multigraph decomposition problems and their computational complexity
- Edge exchanges in Hamiltonian decompositions of Kronecker-product graphs
- On the complexity of some edge-partition problems for graphs
- Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints
- On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem
- Clique partitioning with value-monotone submodular cost
- Mutual exclusion scheduling with interval graphs or related classes. II
- Multigraph decomposition into stars and into multistars
- Edge decompositions and rooted packings of graphs
- Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints
- Graphs having the local decomposition property
- Input-output decomposition of dynamic systems is NP-complete
- scientific article; zbMATH DE number 4101253 (Why is no real title available?)
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- scientific article; zbMATH DE number 1472110 (Why is no real title available?)
- On rooted packings, decompositions, and factors of graphs
- Towards a solution of the Holyer's problem
- Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube
- Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
- Clique and anticlique partitions of graphs
- Equitable colorings of bounded treewidth graphs
This page was built for publication: NP-completeness of graph decomposition problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1179032)
