|
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 www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2014}, |
| NUMBER | = | {TR-2014-02} |