Subgraphs Preserving Local Rooted Edge-Connectivity in Acyclic Digraphs

Assume that a directed graph D with a root node r is given. A beautiful, simple and classic result of Lov´asz claims that the minimum size of a spanning subgraph of D that preserves all local rooted edge-connectivity values λ(r, v) attains a trivial lower bound and that such a subgraph can be found in strongly polynomial time. However, the complexity of finding the minimum weight of such a subgraph is unknown. In this talk we will focus on the special case where D is acyclic. We recently proved that the problem is solvable in strongly polynomial in this special case. As a new result we will prove a minimax formula on the minimum weight of such a subgraph and from this we also derive a polyhedral result.