Open Collections

Poremba, Joseph Chester

University of British Columbia

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.

Text

2022-08-26

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/82556

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/