The GNRS conjecture for minor-free network flow
A graph contains $H$ as a minor if $H$ can be obtained from it by edge contractions and edge or vertex deletions. For a finite connected simple graph $G = (V, E)$ with edge lengths $\ell : E \to [0, \infty)$, let $d_\ell$ be the shortest-path distance on $V$; distinct vertices may be at distance zero. By results of Linial, London and Rabinovich and of Gupta, Newman, Rabinovich and Sinclair, the largest $\ell_1$ distortion of the metrics $d_\ell$ on a fixed graph $G$, over all $\ell$, equals the largest ratio on $G$ between the sparsest-cut value $\Phi$ and the maximum concurrent multicommodity flow $\lambda^*$, over all capacities and demands. So the problem below is equivalent to asking for a constant $C_H$ with $\Phi / C_H \le \lambda^* \le \Phi$ for every fractional multicommodity flow instance on a supply graph without an $H$ minor, the demand pairs being arbitrary. Gupta, Newman, Rabinovich and Sinclair proved it for series-parallel graphs ($H = K_4$). Lee and Sidiropoulos proved it when $H$ is a forest, and showed that it is equivalent to the conjunction of its case for planar graphs and their conjecture on $k$-sums of graphs.
Problem. Fix a finite simple graph $H$. Is there a finite constant $C_H \ge 1$, depending only on $H$, such that for every finite connected simple graph $G = (V, E)$ with no $H$ minor and every $\ell : E \to [0, \infty)$ there are an integer $m \ge 1$ and a map $f : V \to \mathbb{R}^m$ with $$d_\ell(u, v) \le \|f(u) - f(v)\|_1 \le C_H\, d_\ell(u, v) \qquad \text{for all } u, v \in V?$$ The dimension $m$ and the map $f$ may depend on $(G, \ell)$; the constant may not.
Source: Gupta, Newman, Rabinovich and Sinclair (1999; journal version 2004), the conjecture in §3; see Lee and Sidiropoulos (2009), Conjecture 1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG, OC
- Keywords
- AIM Open Applied Problems, graph minors, metric embeddings, multicommodity flows
References
@article{gupta2004,
author = {Gupta, Anupam and Newman, Ilan and Rabinovich, Yuri and Sinclair, Alistair},
title = {Cuts, trees and {$\ell_1$}-embeddings of graphs},
journal = {Combinatorica},
volume = {24},
number = {2},
year = {2004},
pages = {233--269},
doi = {10.1007/s00493-004-0015-x},
}
@inproceedings{gupta1999,
author = {Gupta, Anupam and Newman, Ilan and Rabinovich, Yuri and Sinclair, Alistair},
title = {Cuts, trees and {$\ell_1$}-embeddings of graphs},
booktitle = {40th Annual Symposium on Foundations of Computer Science},
publisher = {IEEE Computer Society},
year = {1999},
pages = {399--408},
doi = {10.1109/SFFCS.1999.814611},
}
@inproceedings{lee2009,
author = {Lee, James R. and Sidiropoulos, Anastasios},
title = {On the geometry of graphs with a forbidden minor},
booktitle = {Proceedings of the 41st Annual ACM Symposium on Theory of Computing},
publisher = {ACM},
year = {2009},
pages = {245--254},
doi = {10.1145/1536414.1536450},
}
@article{linial1995,
author = {Linial, Nathan and London, Eran and Rabinovich, Yuri},
title = {The geometry of graphs and some of its algorithmic applications},
journal = {Combinatorica},
volume = {15},
number = {2},
year = {1995},
pages = {215--245},
doi = {10.1007/BF01200757},
}
@misc{aim-gnrs-minor-free-flow-cut,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The GNRS conjecture for minor-free network flow}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/487-gnrs-minor-free-flow-cut.md},
note = {Entry 487 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00438, "The GNRS conjecture for minor-free network flow", clopen.solutions.