Cut-sufficient directed 2-commodity multiflow topologies

• 成果类型: Article; Early Access
• 署名作者: Poremba, Joseph; Shepherd, F. Bruce
• 署名单位: University of British Columbia
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02195-3
• 发表日期: 2025
• 关键词: flow min-cut; multicommodity flows; approximation; graphs

摘要

In multicommodity network flows, a supply-demand graph pair (G, H) (called a multiflow topology) is cut-sufficient if, for all capacity and demand weights, the cut condition is enough to guarantee the existence of a feasible multiflow. We characterize cut-sufficiency for two classes of directed 2-commodity flows: roundtrip demands, where H is a 2-cycle, and 2-path demands, where H is a directed path of length two. We then extend these characterizations to some larger demand graphs, namely directed stars and directed triangles. To obtain such characterizations, we introduce a theory of relevant minors. Unlike the undirected setting, for directed graphs the cut-sufficient topologies are not minor-closed. They are however relevant-minor-closed. A single forbidden relevant minor characterizes roundtrip cut-sufficiency, and two suffice for the other classes. We also provide a partial characterization in the case of two independent demands (2-matching demands), showing that one of two relevant minors exists if the weights that break cut-sufficiency have unit demand values. As an application of our results, we show that recognizing cut-sufficiency for directed multiflow topologies is co-NP-hard, even for roundtrip demands. This is in contrast to undirected 2-commodity flows, for which topologies are always cut-sufficient.