Rooted k-connections in digraphs

András Frank


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:

AUTHOR = {Frank, Andr{\'a}s},
TITLE = {Rooted k-connections in digraphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2006},
NUMBER = {TR-2006-07}

Last modification: 29.12.2020. Please email your comments to Tamás Király!