arXiv:2611.12330 · v1

Cut Conditions, Integrality, and Obstructions for Directed Multiflows

首次提交 2026-11-09 20:48

版本更新 2026-11-09 20:48

雷达观测 2026-11-10 15:22

摘要

In contrast to the max-flow/min-cut theorem for single-commodity flows, the cut condition is necessary but not sufficient for the existence of directed multiflows, even with only two commodities. Poremba and Shepherd (IPCO 2023) conjecture that the cut condition is sufficient for all capacities and demands on a directed two-commodity topology if and only if it contains neither of two specific topologies as a relevant minor. We prove this conjecture. As a consequence, the fractional and integral flow-cut gaps of every directed two-commodity topology coincide and are either 1 or 2. We then investigate stronger necessary conditions for multiflow feasibility and their implications for integrality. We introduce a hierarchy of five conditions, ranging from the classical cut condition through conditions based on blocking edge sets and binary edge lengths to the linear programming dual characterization of fractional feasibility. The corresponding classes of sufficient topologies are strictly nested. We extend the Nagamochi-Ibaraki theorem: whenever one of the first four conditions is sufficient on a topology, integral capacities and demands satisfying that condition admit an integral multiflow, computable in polynomial time. Finally, we prove that recognizing topologies on which any of these four conditions is sufficient is coNP-complete, even for two commodities.