Polynomial cases of graph decomposition: A complete solution of Holyer’s problem

Let HH be a fixed graph. A graph GG has an HH-decomposition if the edge set of GG can be partitioned into subsets inducing graphs isomorphic to HH. Let PHPH denote the following decision problem: “Does an instance graph GG admit HH-decomposition?” In this paper we prove that the problem PHPH is polynomial time solvable if HH is a graph whose every component has at most 2 edges. This way we complete a solution of Holyer’s problem which is the problem of classifying the problems PHPH according to their computational complexities.