Complexity results on the decomposition of a digraph into directed linear forests and out-stars

Abstract

We consider two decomposition problems in directed graphs. We say that a digraph is $k$-bounded for some $k\in {\mathbb{Z}}_{\ge 1}$ if each of its connected components contains at most $k$ arcs. For the first problem, a directed linear forest is a collection of vertex-disjoint directed paths and we consider the problem of decomposing a given digraph into a $k$-bounded and an $\ell$-bounded directed linear forest for some fixed $k,\ell \in {\mathbb{Z}}_{\ge 1}\cup \{\infty \}$. We give a full dichotomy for this problem by showing that it can be solved in polynomial time if $k+\ell \le 3$ and is NP-complete otherwise. This answers a question of Campbell, Hörsch, and Moore. For the second problem, we say that an out-galaxy is a vertex-disjoint collection of out-stars. Again, we give a full dichotomy of when a given digraph can be edge-decomposed into a $k$-bounded and an $\ell$-bounded out-galaxy for fixed $k,\ell \in {\mathbb{Z}}_{\ge 1}\cup \{\infty \}$. More precisely, we show that the problem can be solved in polynomial time if $\min \{k,\ell \}\in \{1,\infty \}$ and is NP-complete otherwise.