Embeddings of Planar Quasimetrics into Directed ℓ1 and Polylogarithmic Approximation for Directed Sparsest-Cut
Ken‐ichi Kawarabayashi, Anastasios Sidiropoulos · 2022
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 [20] and by Aumann and Rabani [5] that for general n-vertex graphs it is bounded by O(log n) and the Gupta-Newman-Rabinovich-Sinclair conjecture [13] asserts that it is O(1) for any family of graphs that excludes some fixed minor. We show that the multicommodity flow-cut gap on directed planar graphs is O(log3n). This is the first sub-polynomial bound for any family of directed graphs of super-constant treewidth. We remark that for general directed graphs, it has been shown by Chuzhoy and Khanna [11] that the gap is Ω(n1/7), even for directed acyclic graphs. As a direct consequence of our result, we also obtain the first polynomial-time polylogarithmic-approximation algorithms for the Directed Non-Bipartite Sparsest-Cut, and the Directed Multicut problems for directed planar graphs, which extends the long-standing result for undirectd planar graphs by Rao [22] (with a slightly weaker bound). At the heart of our result we investigate low-distortion quasimetric embeddings into directed$e$1. More precisely, we construct O(log2n)-Lipschitz quasipartitions for the shortest-path quasimetric spaces of planar digrap$hs$, which generalize the notion of Lipschitz partitions from the theory of metric embeddings. This construction combines ideas from the theory of bi-Lipschitz embeddings, with tools form data structures on directed planar graphs.