On spanning galaxies in digraphs

In a directed graph, a star is an arborescence with at least one arc, in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. In this paper, we consider the Spanning Galaxy problem of deciding whether a digraph DD has a spanning galaxy or not. We show that although this problem is NP-complete (even when restricted to acyclic digraphs), it becomes polynomial-time solvable when restricted to strong digraphs. In fact, we prove that restricted to this class, the Spanning Galaxy problem is equivalent to the problem of deciding whether a strong digraph has a strong subdigraph with an even number of vertices. We then show a polynomial-time algorithm to solve this problem. We also consider some parameterized version of the Spanning Galaxy problem. Finally, we improve some results concerning the notion of directed star arboricity of a digraph DD, which is the minimum number of galaxies needed to cover all the arcs of DD. We show in particular that dst(D)≤Δ(D)+1dst(D)≤Δ(D)+1 for every digraph DD and that dst(D)≤Δ(D)dst(D)≤Δ(D) for every acyclic digraph DD.

► Deciding whether a digraph has a spanning galaxy is NP-complete.
► A strong digraph has a spanning galaxy iff it has an even strong subdigraph.
► Polynomial algorithm for finding an even strong subdigraph of a given strong digraph has been presented.
► For every digraph DD its directed star arboricity is at most Δ+1Δ+1.