SIAM Journal on Computing · 1997 · 135 citations · 7 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsComputational GeometryDirected Acyclic GraphsGraph AlgorithmsGraph TheoryAlgorithmic Graph TheoryComputational Complexity Of Graph AlgorithmsDecompositionsGraph DecompositionsNp-complete ProblemsNp-completenessSubgraph Isomorphism
An H-decomposition of a graph G=(V,E) is a partition of E into subgraphs isomorphic to H. Given a fixed graph H, the H-decomposition problem is to determine whether an input graph G admits an H-decomposition. In 1980, Holyer conjectured that H-decomposition is NP-complete whenever H is connected and has three edges or more. Some partial results have been obtained since then. A complete proof of Holyer's conjecture is the content of this paper. The characterization problem of all graphs H for which H-decomposition is NP-complete is hence reduced to graphs where every connected component contains at most two edges.
7
The NP-Completeness of Some Edge-Partition Problems
Ian Holyer · SIAM Journal on Computing · 1981 · 218 citations
On the completeness of a generalized matching problem
David Kirkpatrick, Pavol Hell · 1978 · 165 citations · Full text
NP-Completeness of graph decomposition problems
Edith Cohen, Michael Tarsi · Journal of Complexity · 1991 · 47 citations