TR-2006-07

Rooted k-connections in digraphs

András Frank



Abstract

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}
}


Last modification: 30.10.2014. Please email your comments to Jácint Szabó!