A node-capacitated Okamura-Seymour theorem

DOI10.1145/2488608.2488671zbMATH Open1322.05068arXiv1209.2744OpenAlexW3121660951MaRDI QIDQ747769FDOQ747769

Mohammad Moharrami, James R. Lee, Manor Mendel

Publication date: 19 October 2015

Published in: Mathematical Programming. Series A. Series B, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: The classical Okamura-Seymour theorem states that for an edge-capacitated, multi-commodity flow instance in which all terminals lie on a single face of a planar graph, there exists a feasible concurrent flow if and only if the cut conditions are satisfied. Simple examples show that a similar theorem is impossible in the node-capacitated setting. Nevertheless, we prove that an approximate flow/cut theorem does hold: For some universal c > 0, if the node cut conditions are satisfied, then one can simultaneously route a c-fraction of all the demands. This answers an open question of Chekuri and Kawarabayashi. More generally, we show that this holds in the setting of multi-commodity polymatroid networks introduced by Chekuri, et. al. Our approach employs a new type of random metric embedding in order to round the convex programs corresponding to these more general flow problems.

Full work available at URL: https://arxiv.org/abs/1209.2744

zbMATH Keywords

multicommodity flowsmetric embeddingsmulticommodity polymatroid networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21)

Cites Work

• Maximal Flow Through a Network
• Extending Lipschitz functions via random metric partitions
• The geometry of graphs and some of its algorithmic applications
• Measured descent: A new embedding method for finite metrics
• Title not available (Why is that?)
• Minimum cost flow with set-constraints
• Computing Maximal “Polymatroidal” Network Flows
• Multi-Commodity Network Flows
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• The metrical interpretation of superreflexivity in Banach spaces
• Vertex cuts, random walks, and dimension reduction in series-parallel graphs
• Excluded minors, network decomposition, and multicommodity flow
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Multicommodity flows in planar graphs
• On the geometry of graphs with a forbidden minor
• Multicommodity flows and cuts in polymatroidal networks
• Edge-Disjoint Paths in Planar Graphs with Constant Congestion
• An algorithm for node-capacitated ring routing
• Approximation algorithms for the 0-extension problem
• Node-Capacitated Ring Routing
• Vertex Sparsifiers: New Results from Old Techniques
• On dominated \(\ell_1\) metrics

Cited In (3)

• Multicommodity flows and cuts in polymatroidal networks
• Title not available (Why is that?)
• Improved Guarantees for Vertex Sparsification in Planar Graphs

This page was built for publication: A node-capacitated Okamura-Seymour theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q747769)