Edge decompositions and rooted packings of graphs (Q2675822)

In this paper, the problem of edge decomposition of graphs is considered from the viewpoint of computational complexity. For a fixed family of graphs \(\mathcal{H}\), given a graph \(G\), the graph decomposition problem DEC(\(\mathcal{H}\)) asks whether there is an edge decomposition of \(G\) into the members of \(\mathcal{H}\), which is called an \(\mathcal{H}\)-decomposition. When \(\mathcal{H}\) consists of just one graph \(H\), there is a dichotomous result stating that if every component of the graph \(H\) has one or two edges then the problem DEC(\(\{H\}\)) is polynomial-time solvable; otherwise, it is NP-complete. In this paper, the computational complexity of the problem DEC (\(\{2K_2,H\}\)) is studied. The authors give a partial solution to the problem by showing that for some large classes of graphs \(H\) this problem is polynomial-time solvable, while for some other large classes of graphs it is NP-complete. In the proofs, the so-called rooted packings into graphs which are mutual generalizations of both edge decompositions and factors of graphs are applied.