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

Let 𝐻 be a fixed graph. A graph 𝐺 has an 𝐻 -decomposition if the edge set of 𝐺 can be partitioned into subsets inducing graphs isomorphic to 𝐻 . Let 𝑃 𝐻 denote the following decision problem: “Does an instance graph 𝐺 admit 𝐻 -decomposition?” In this paper we prove that the problem 𝑃 𝐻 is polynomial time solvable if 𝐻 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 𝑃 𝐻 according to their computational complexities. In 1981 Holyer published a short paper [13] in which he proved that the problem to decide if, for a fixed 𝑝 ≥ 3 , the set of edges of a graph can be partitioned into subsets inducing complete graphs 𝐾 𝑝 is NP-complete. He also showed a similar result for cycles of length at least 3. In view of these results a natural problem, known as the Holyer problem, arises. The Holyer Problem:Given a fixed graph 𝐻 , what is the computationa

Let 𝐻 be a fixed graph. A graph 𝐺 has an 𝐻 -decomposition if the edge set of 𝐺 can be partitioned into subsets inducing graphs isomorphic to 𝐻 . Let 𝑃 𝐻 denote the following decision problem: “Does an instance graph 𝐺 admit 𝐻 -decomposition?” In this paper we prove that the problem 𝑃 𝐻 is polynomial time solvable if 𝐻 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 𝑃 𝐻 according to their computational complexities. In 1981 Holyer published a short paper [13] in which he prov