|
The problem of covering minimum cost common bases of two matroids is
NP-complete, even if the two matroids coincide, and the costs are all
equal to 1. In this paper we show that the following special case is
solvable in polynomial time: given a digraph $D=(V,A)$ with a
designated root node $r\in V$ and arc-costs $c:A\to \Rset$, find a
minimum cardinality subset $H$ of the arc set $A$ such that $H$
intersects every minimum $c$-cost $r$-arborescence. By an
$r$-arborescence we mean a spanning arborescence of root $r$. The
algorithm we give solves a weighted version as well, in which a
nonnegative weight function $w:A\to \Rset_+$ (unrelated to $c$) is
also given, and we want to find a subset $H$ of the arc set such that
$H$ intersects every minimum $c$-cost $r$-arborescence, and
$w(H)=\sum_{a\in H}w(a)$ is minimum. The running time of the algorithm
is $O(n^3T(n,m))$, where $n$ and $m$ denote the number of nodes and
arcs of the input digraph, and $T(n,m)$ is the time needed for a
minimum $s-t$ cut computation in this digraph. A polyhedral
description is not given, and seems rather challenging.
This is a revised and extended version of report no. 2011-13.
Bibtex entry:
| AUTHOR | = | {Bern{\'a}th, Attila and Pap, Gyula}, |
| TITLE | = | {Blocking optimal arborescences}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2015}, |
| NUMBER | = | {TR-2015-06} |