Edge Decomposition into Isomorphic Copies ofsK1, 2Is Polynomial

LetHbe a fixed graph. We say that a graphGadmits anH-decomposition if the set of edges ofGcan be partitioned into subsets generating graphs isomorphic toH. Denote by PHthe problem of exisitence of anH-decomposition of a graph. The Holyer problem is to classify the problems PHaccording to their computational complexities. In this paper we show that the problem PHis polynomial whenHis the union ofsdisjoint 2-edge paths.