Complexity Results on the Decomposition of a Digraph into Directed Linear Forests and Out-Stars - Hörsch, Florian; Picasarri-Arrieta, Lucas (The Electronic Journal of Combinatorics, 2024)
We consider two decomposition problems in directed graphs. We say that a digraph is $k$-bounded for some $k \in \mathbb{Z}_{≥ 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}_{≥ 1}\cup \{∞\}$. We give a full dichotomy for this problem by showing that it can be solved in polynomial time if $k+\ell ≤ 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}_{≥ 1}\cup \{∞\}$. More precisely, we show that the problem can be solved in polynomial time if $\min\{k,\ell\}\in \{1,∞\}$ and is NP-complete otherwise.