Subgraphs Preserving Local Rooted Edge-Connectivity in Acyclic Digraphs

Szeszlér, Dávid (2025) Subgraphs Preserving Local Rooted Edge-Connectivity in Acyclic Digraphs. In: 13th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2025.05.26-2025.05.29, Tokyo.

Preview

Text HJ2025_proceedings_szeszler.pdf - Published Version Download (430kB) | Preview

Abstract

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.

Actions (login required)

Edit Item