Parameterized Algorithms for Non-separating Trees and Branchings in Digraphs

Abstract

A well known result in graph algorithms, due to Edmonds, states that given a digraph D and a positive integer ℓ, we can test whether D contains ℓ 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.