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 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 -bounded directed linear forest for some fixed k,Z_≥ 1{∞}. We give a full dichotomy for this problem by showing that it can be solved in polynomial time if k+≤ 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 -bounded out-galaxy for fixed k,Z_≥ 1{∞}. More precisely, we show that the problem can be solved in polynomial time if {k,}{1,∞} and is NP-complete otherwise.