2017/11/04 by Ario Salmasi, Salmasi, Ario, Anastasios Sidiropoulos +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1711.01370
openalex publication_date 2017/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The multi-commodity flow-cut gap is a fundamental parameter that affects the performance of several divide & conquer algorithms, and has been extensively studied for various classes of undirected graphs. It has been shown by Linial, London and Rabinovich \citelinial1994geometry and by Aumann and Rabani \citeaumann1998log that for general n-vertex graphs it is bounded by O(log n) and the Gupta-Newman-Rabinovich-Sinclair conjecture \citegupta2004cuts asserts that it is O(1) for any family of graphs that excludes some fixed minor. The flow-cut gap is poorly understood for the case of directed graphs. We show that for uniform demands it is O(1) on directed series-parallel graphs, and on directed graphs of bounded pathwidth. These are the first constant upper bounds of this type for some non-trivial family of directed graphs. We also obtain O(1) upper bounds for the general multi-commodity flow-cut gap on directed trees and cycles. These bounds are obtained via new embeddings and Lipschitz quasipartitions for quasimetric spaces, which generalize analogous results form the metric case, and could be of independent interest. Finally, we discuss limitations of methods that were developed for undirected graphs, such as random partitions, and random embeddings.