Rooted kk-connections in digraphs

The problem of computing a minimum cost subgraph D′=(V,A′)D′=(V,A′) of a directed graph D=(V,A)D=(V,A) so as to contain kk edge-disjoint paths from a specified root r0∈Vr0∈V to every other node in VV was solved by Edmonds [J. Edmonds, Submodular functions, matroids, and certain polyhedra, in: R. Guy, H. Hanani, N. Sauer, J. Schönheim (Eds.), Combinatorial Structures and their Applications, Gordon and Breach, New York, 1970, pp. 69–87] by an elegant reduction to weighted matroid intersection. A corresponding problem when openly disjoint paths are requested rather than edge-disjoint ones was solved in [A. Frank, É. Tardos, An application of submodular flows, Linear Algebra Appl. 114–115 (1989) 329–348] 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 kk-connection problems reduces to matroid intersection. The approach is based on a new matroid construction extending what Whiteley [W. Whiteley, Some matroids from discrete applied geometry, in: J.E. Bonin, J.G. Oxley, B. Servatius (Eds.), Matroid Theory, in: Contemp. Math., vol. 197, Amer. Math. Soc, Providence, RI, 1996, pp. 171–311] calls count matroids. We also provide a polyhedral description using supermodular functions on bi-sets and this approach enables us to handle more general rooted kk-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)D=(V,A) with a root-node r0r0, a terminal set TT, and a cost function c:A→R+ so that each edge of positive cost has its head in TT, find a subgraph D′=(V,A′)D′=(V,A′) of DD of minimum cost so that there are kk openly disjoint paths in D′D′ from r0r0 to every node in TT.