Blocking unions of arborescences

Attila Bernáth, Gyula Pap


Given a digraph $D=(V,A)$ and a positive integer $k$, a subset $B\subseteq A$ is called a $k$-union-arborescence, if it is the disjoint union of $k$ spanning arborescences. When also arc-costs $c:A\to \Rset_+$ are given, minimizing the cost $k$-union-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 if which destroys every minimum $c$-cost $k$-union-arborescence. Actually, the more general weighted problem is also considered, that is, arc weights $w:A\to \Rset_+$ (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$-union-arborescence. An equivalent version of this problem is where the roots of the arborescences are fixed in advance. In an earlier paper 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$-union-arbosercences. Our algorithm runs in polynomial time for this problem. The solution uses a result of Bárász, Becker and Frank saying that the family of so-called insolid 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.

Previous version can be found here.

Bibtex entry:

AUTHOR = {Bern{\'a}th, Attila and Pap, Gyula},
TITLE = {Blocking unions of arborescences},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2014},
NUMBER = {TR-2014-02}

Last modification: 29.12.2020. Please email your comments to Tamás Király!