Back to search

University of British Columbia

Directed multicommodity flows : cut-sufficiency and forbidden relevant minors

Abstract

dc:description

In a multicommodity flow problem, the goal is to route paths in a supply graph G to satisfy demands between vertices, represented by a demand graph H. This must be done simultaneously for all commodities, without exceeding edge capacities. To do this, there can be no cut where the requested demand exceeds the available capacity. This is called the cut condition. The Max-Flow Min-Cut Theorem states that for single-commodity flows, the cut condition guarantees that a feasible routing exists. This fails for general multicommodity flows. A supply-demand graph pair (G,H) is cut-sufficient if, for all capacity and demand weights, the cut condition implies feasibility. Many results are known for undirected cut-sufficiency. For instance, the cut-sufficient pairs with series-parallel supply graphs have a forbbiden-minor characterization. However, less is known about cut-sufficiency for directed multicommodity flows. We characterize cut-sufficiency for several classes of directed multicommodity flow problems. We consider pairs with roundtrip or two-path demands, where H is a 2-cycle and 2-path, respectively. We prove that the cut-sufficient pairs in these classes are characterized by one and two forbidden minors, respectively. We also consider pairs with two disjoint demands. For these, we give a forbidden-minor characterization of the pairs that are cut-sufficient for unit demands, and conjecture about their cut-sufficiency with arbitrary weights. Unlike the undirected case, for directed graphs the class of cut-sufficient pairs is not closed under taking minors. To solve this, we develop a theory of relevant minors, which restricts permitted contractions to restore the closure of cut-sufficiency. Our characterizations are in terms of forbidden relevant minors. As an application of our results, we show that recognizing cut-sufficiency is NP-hard for roundtrip demands. This contrasts with undirected two-commodity flows, for which supply-demand graph pairs are always cut-sufficient. We also provide a primal proof of the fact that any orientation of an undirected tree is cut-sufficient with any directed demand graph. This was previously known, but was proven via the dual method of metric embeddings. We prove trees are the only graphs with this property.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Poremba, Joseph Chester
Contributors dc:contributor
  • Shepherd, F. Bruce (Frederick Bruce)

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/82556

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Poremba, Joseph Chester. Directed multicommodity flows : cut-sufficiency and forbidden relevant minors. master's thesis, University of British Columbia, 2022. http://hdl.handle.net/2429/82556