# Coarse Differentiation and Multi-flows in Planar Graphs

@article{Lee2008CoarseDA, title={Coarse Differentiation and Multi-flows in Planar Graphs}, author={James R. Lee and Prasad Raghavendra}, journal={Discrete \& Computational Geometry}, year={2008}, volume={43}, pages={346-362} }

AbstractWe show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound (Chakrabarti et al. in 49th Annual Symposium on Foundations of Computer Science, pp. 761–770, 2008) for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair.This also improves the largest known gap for planar graphs from
$\frac{3}{2}$
to 2, yielding the first lower bound that does not follow from elementary… Expand

#### 36 Citations

Flow-Cut Gaps and Face Covers in Planar Graphs

- Mathematics, Computer Science
- SODA
- 2019

It is proved that the flow-cut gap is $O(\gamma)$ for vertex-capacitated instances when the terminals lie on at most $\gamma$ faces, by showing that the edge-weighted shortest-path metric induced on the terminals admits a stochastic embedding into trees with distortion, which is tight. Expand

On the geometry of graphs with a forbidden minor

- Mathematics, Computer Science
- STOC '09
- 2009

We study the topological simplification of graphs via random embeddings, leading ultimately to a reduction of the Gupta-Newman-Rabinovich-Sinclair (GNRS) L1 embedding conjecture to a pair of… Expand

A Quasipolynomial $(2+\varepsilon)$-Approximation for Planar Sparsest Cut

- Computer Science
- 2021

This work considers the problem for planar graphs, and gives a (2 + ε)-approximation algorithm that runs in quasipolynomial time, and defines a new structural decomposition of an optimal solution using a “patching” primitive. Expand

A quasipolynomial (2 + ε)-approximation for planar sparsest cut

- Computer Science
- STOC
- 2021

This work considers the problem for planar graphs, and gives a (2+)-approximation algorithm that runs in quasipolynomial time, and defines a new structural decomposition of an optimal solution using a “patching” primitive. Expand

Pathwidth, trees, and random embeddings

- Mathematics, Computer Science
- Comb.
- 2013

We prove that, for every integer k≥1, every shortest-path metric on a graph of pathwidth k embeds into a distribution over random trees with distortion at most c=c(k), independent of the graph size.… Expand

Metric embedding via shortest path decompositions

- Computer Science, Mathematics
- STOC
- 2018

The main result is an O(kmin{1p,12})-distortion embedding, which is a super-exponential improvement over the best previous bound of Lee and Sidiropoulos and implies improved distortion on bounded treewidth graphs (O((klogn)1p)). Expand

On the 2-sum embedding conjecture

- Computer Science, Mathematics
- SoCG '13
- 2013

It is proved that the 2-sum embedding conjecture holds for any finite family of graphs, and any path metric on a graph formed by 2-sums of arbitrarily many copies of <i>K</i><sub><i>n</i></sub> embeds into <i>, with distortion <i*O</i>(log <i’n>). Expand

A face cover perspective to 𝓁1 embeddings of planar graphs

- Computer Science
- SODA
- 2020

This work studies the case where there is a set K of terminals, and the goal is to embed only the terminals into `1 with low distortion, and provides a polynomial time O( √ log γ) approximation to the sparsest cut problem on planar graphs, for the cases where all the demand pairs can be covered by γ faces. Expand

A face cover perspective to $\ell_1$ embeddings of planar graphs

- Mathematics, Computer Science
- SODA 2019
- 2019

This work provides a polynomial time approach to the sparsest cut problem on planar graphs, for the case where all the demand pairs can be covered by $\gamma$ faces. Expand

Sparsest cut on bounded treewidth graphs: algorithms and hardness results

- Computer Science, Mathematics
- STOC '13
- 2013

It is shown that even for treewidth-2 graphs, the LP has an integrality gap close to 2 even after polynomially many rounds of Sherali-Adams, so the approach cannot be improved even on such restricted graphs without using a stronger relaxation. Expand

#### References

SHOWING 1-10 OF 40 REFERENCES

Expander flows, geometric embeddings and graph partitioning

- Mathematics, Computer Science
- STOC '04
- 2004

An interesting and natural "certificate" for a graph's expansion is described, by embedding an n-node expander in it with appropriate dilation and congestion, and is called an expander flow. Expand

On multicommodity flows in planar graphs

- Mathematics, Computer Science
- Networks
- 1984

It is shown, by presenting counterexamples, that the half-integrality property does not necessarily hold when either the graph cannot be drawn in the plane with all sources and sinks on a common face, or the graph is directed. Expand

The geometry of graphs and some of its algorithmic applications

- Computer Science, Mathematics
- Comb.
- 1995

Efficient algorithms for embedding graphs low-dimensionally with a small distortion, and a new deterministic polynomial-time algorithm that finds a (nearly tight) cut meeting this bound. Expand

Vertex cuts, random walks, and dimension reduction in series-parallel graphs

- Mathematics, Computer Science
- STOC '07
- 2007

It is shown that series-parallel metrics have Markov type 2, which generalizes a result of Naor, Peres, Schramm, and Sheffield for trees and yields an O(√log n) approximation algorithm for vertex sparsestcut in such graphs, as well as an O(*log k) approximate max-flow/min-vertex-cut theorem for series- parallel instances with<i>k</i> terminals. Expand

Embedding k-outerplanar graphs into ℓ1

- Computer Science, Mathematics
- SODA '03
- 2003

It is shown that the shortest-path metric of any k-outerplanar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion, and hence also embedded into l1 with constant distort, implying a constant upper bound on the ratio between the sparsest cut and the maximum concurrent flow in multicommodity networks for k- outerplanar graphs. Expand

Cuts, Trees and ℓ1-Embeddings of Graphs*

- Computer Science, Mathematics
- Comb.
- 2004

It is shown, surprisingly, that such metrics approximate distances very poorly even for families of graphs with low treewidth, and excludes the possibility of using them to explore the finer structure of ℓ1-embeddability. Expand

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1

- Mathematics, Computer Science
- FOCS
- 2005

This paper disproves the non-uniform version of Arora, Rao and Vazirani's Conjecture (2004), asserting that the integrality gap of the sparsest cut SDP, with the triangle inequality constraints, is bounded from above by a constant. Expand

Geometry of cuts and metrics

- Computer Science
- Algorithms and combinatorics
- 1997

This book draws from the interdisciplinarity of these fields as it gathers methods and results from polytope theory, geometry of numbers, probability theory, design and graph theory around two objects, cuts and metrics. Expand

Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums

- Mathematics, Computer Science
- 2008 49th Annual IEEE Symposium on Foundations of Computer Science
- 2008

We study the properties of embeddings, multicommodity flows, and sparse cuts in minor-closed families of graphs which are also closed under 2-sums; this includes planar graphs, graphs of bounded… Expand

An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm

- Mathematics, Computer Science
- SIAM J. Comput.
- 1998

It is shown that the minimum cut ratio is within a factor of O(log k) of the maximum concurrent flow for k-commodity flow instances with arbitrary capacities and demands, and thus of the optimal min-cut ratio. Expand