Blocking unions of arborescences

Abstract Given a digraph D = ( V , A ) and a positive integer k , a subset B ⊆ A is called a k -arborescence, if it is the disjoint union of k spanning arborescences. When also arc-costs c : A → R are given, minimizing the cost of a k -arborescence is well-known to be tractable. In this paper we take on the following problem: what is the minimum cardinality of a set of arcs the removal of which destroys every minimum c -cost k -arborescence. Actually, the more general weighted problem is also considered, that is, arc weights w : A → R + (unrelated to c ) are also given, and the goal is to find a minimum weight set of arcs the removal of which destroys every minimum c -cost k -arborescence. An equivalent version of this problem is where the roots of the arborescences are fixed in advance. In an earlier paper (Bernath and Pap, 2013) we solved this problem for k = 1 . This work reports on other partial results on the problem. We solve the case when both c and w are uniform—that is, find a minimum size set of arcs that covers all k -arborescences. Our algorithm runs in polynomial time for this problem. The solution uses a result of Barasz et al. (2005) saying that the family of so-called in-solid sets (sets with the property that every proper subset has a larger in-degree) satisfies the Helly-property, and thus can be (efficiently) represented as a subtree hypergraph. We also give an algorithm for the case when only c is uniform but w is not. This algorithm is only polynomial if k is not part of the input.