Blocking optimal arborescences

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

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 R$ , 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 R_{+}$ (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^{3} T (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.

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

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 R$ , 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 R_{+}$ (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^{3} T (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.

文献摘要