Approximately Packing Dijoins Via Nowhere-Zero Flows
summary
Proves a concrete packing bound: if the underlying undirected graph admits a nowhere-zero k-flow, then a digraph with minimum dicut size τ contains ⌊τ/k⌋ arc-disjoint dijoins; plugging Younger's/Seymour k=6 yields at least τ/6 dijoins. Method: orient the undirected graph by the flow, split arcs by agreement (ceil/floor) to produce two τ/k–arc-connected subgraphs, use Edmonds arborescence packing to extract in- and out-trees and pair them into strongly connected subgraphs, giving an explicit, strongly‑polynomial algorithm.
AI-written summary · about