The complexity of decomposing a graph into a matching and a bounded linear forest

Abstract

Deciding whether a graph can be edge-decomposed into a matching and a $k$-bounded linear forest was recently shown by Campbell, H{ö}rsch and Moore to be NP-complete for every $k\ge 9$, and solvable in polynomial time for $k=1,2$. In the first part of this paper, we close this gap by showing that this problem is in NP-complete for every $k\ge 3$. In the second part of the paper, we show that deciding whether a graph can be edge-decomposed into a matching and a $k$-bounded star forest is polynomially solvable for any $k\in \mathbb{N}\cup \{\infty \}$, answering another question by Campbell, H{ö}rsch and Moore from the same paper.

17 pages, 10 figures