Scholarlink

<p>In multicommodity network flows, a supply–demand graph pair (<i>G</i>,&#xa0;<i>H</i>) (called a <i>multiflow topology</i>) is <i>cut-sufficient</i> 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: <i>roundtrip</i> demands, where <i>H</i> is a 2-cycle, and <i>2-path</i> demands, where <i>H</i> 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 <i>relevant minors</i>. 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 (<i>2-matching demands</i>), 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Cut-sufficient directed 2-commodity multiflow topologies

  • 期刊论文

  • 发表日期：

    2025年2月3日

查看全文
  • Joseph Poremba,
  • F. Bruce Shepherd

摘要

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.