The problem of computing a minimum cost subgraph D'=(V,A') of a directed graph D=(V,A) so that D' contains k edge-disjoint paths from a specified root r \in V to every other node in V is known to be nicely solvable since it can be formulated as a matroid intersection problem. A corresponding problem when openly disjoint paths are requested rather than edge-disjoint was solved in [12] with the help of submodular flows. Here we show that the use of submodular flows is actually avoidable and even a common generalization of the two rooted k-connection problems is a matroid intersection problem. We also provide a polyhedral description using supermodular functions on bi-sets and this approach enables us to handle more general rooted k-connection problems. For example, with the help of a submodular flow algorithm the following restricted version of the generalized Steiner-network problem is solvable in polynomial time: given a digraph D=(V,A) with a root-node r, a terminal set T, and a cost function c:A \to R_{+} so that each edge of positive cost has its head in T, find a subgraph D'=(V,A') of D of minimum cost so that there are k openly disjoint paths in D' from r to every node in T.
Bibtex entry:
@techreport{egres-06-07,
AUTHOR | = | {Frank, Andr{\'a}s}, |
TITLE | = | {Rooted k-connections in digraphs}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2006}, |
NUMBER | = | {TR-2006-07} |