Parameterized Algorithms for Non-separating Trees and Branchings in Digraphs

A well known result in graph algorithms, due to Edmonds, states that given a digraph D and a positive integer $$\ell $$l, we can test whether D contains $$\ell $$l arc-disjoint out-branchings in polynomial time. However, if we ask whether there exists an out-branching and an in-branching which are arc-disjoint, then the problem becomes NP-complete. In fact, even deciding whether a digraph D contains an out-branching which is arc-disjoint from some spanning tree in the underlying undirected graph remains NP-complete. In this paper we formulate some natural optimization questions around these problems and initiate its study in the realm of parameterized complexity. More precisely, the problems we study are the following: Arc-Disjoint Branchings and Non-Disconnecting Out-Branching. In Arc-Disjoint Branchings (Non-Disconnecting Out-Branching), a digraph D and a positive integer k are given as input and the goal is to test whether there exist an out-branching and in-branching (respectively, a spanning tree in the underlying undirected graph) that differ on at least k arcs. We obtain the following results for these problems. Non-Disconnecting Out-Branching is fixed parameter tractable (FPT) and admits a linear vertex kernel. Arc-Disjoint Branchings is FPT on strong digraphs. The algorithm for Non-Disconnecting Out-Branching runs in time $$2^{\mathcal {O}(k)}n^{\mathcal {O}(1)}$$2O(k)nO(1) and the approach we use to obtain this algorithms seems useful in designing other moderately exponential time algorithms for edge/arc partitioning problems.