|
Published in:
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.
Bibtex entry:
| AUTHOR | = | {Bern{\'a}th, Attila and Pap, Gyula}, |
| TITLE | = | {Blocking unions of arborescences}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2014}, |
| NUMBER | = | {TR-2014-02} |