In theoretical computer science and metric geometry, the GNRS conjecture connects the theory of graph minors, the stretch factor of embeddings, and the approximation ratio of multi-commodity flow problems.
It is named after Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair, who formulated it in 2004.
[1] One formulation of the conjecture involves embeddings of the shortest path distances of weighted undirected graphs into
If an embedding maps all pairs of vertices with distance
For instance, the planar graphs are closed under minors.
Therefore, it would follow from the GNRS conjecture that the planar graphs have bounded distortion.
[1] An alternative formulation involves analogues of the max-flow min-cut theorem for undirected multi-commodity flow problems.
The ratio of the maximum flow to the minimum cut, in such problems, is known as the flow-cut gap.
The largest flow-cut gap that a flow problem can have on a given graph equals the distortion of the optimal
[2][3] Therefore, the GNRS conjecture can be rephrased as stating that the minor-closed families of graphs have bounded flow-cut gap.
[4] Some graphs have logarithmic flow-cut gap, and in particular this is true for a multicommodity flow with every pair of vertices having equal demand on a bounded-degree expander graph.
[5] Therefore, this logarithmic bound on the distortion of arbitrary graphs is tight.
Planar graphs can be embedded with smaller distortion,
[6] Although the GNRS conjecture remains unsolved, it has been proven for some minor-closed graph families that bounded-distortion embeddings exist.
spaces with stretch exactly one by the tight span construction.