GNRS conjecture

Unsolved problem in mathematics:

Do minor-closed graph families have

\ell _{1}

embeddings with bounded distortion?

(more unsolved problems in mathematics)

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]

Formulation

One formulation of the conjecture involves embeddings of the shortest path distances of weighted undirected graphs into $\ell _{1}$ spaces, real vector spaces in which the distance between two vectors is the sum of their coordinate differences. If an embedding maps all pairs of vertices with distance $d$ to pairs of vectors with distance in the range $[cd,Cd]$ then its stretch factor or distortion is the ratio $C/c$ ; an isometry has stretch factor one, and all other embeddings have greater stretch factor.^[1]

The graphs that have an embedding with at most a given distortion are closed under graph minor operations, operations that delete vertices or edges from a graph or contract some of its edges. The GNRS conjecture states that, conversely, every minor-closed family of graphs, other than the family of all graphs, can be embedded into an $\ell _{1}$ space with bounded distortion. That is, the distortion of graphs in the family is bounded by a constant that depends on the family but not on the individual graphs. 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 $\ell _{1}$ embedding of the graph.^[2]^[3] Therefore, the GNRS conjecture can be rephrased as stating that the minor-closed families of graphs have bounded flow-cut gap.^[1]

Related results

Arbitrary $n$ -vertex graphs (indeed, arbitrary $n$ -point metric spaces) have $\ell _{1}$ embeddings with distortion $O(\log n)$ .^[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, $O({\sqrt {\log n}})$ .^[6]

Although the GNRS conjecture remains unsolved, it has been proven for some minor-closed graph families that bounded-distortion embeddings exist. These include the series–parallel graphs and the graphs of bounded circuit rank,^[1] the graphs of bounded pathwidth,^[7] the 2-clique-sums of graphs of bounded size,^[8] and the $k$ -outerplanar graphs.^[9]

In contrast to the behavior of metric embeddings into $\ell _{1}$ spaces, every finite metric space has embeddings into $\ell _{2}$ with stretch arbitrarily close to one by the Johnson–Lindenstrauss lemma, and into $\ell _{\infty }$ spaces with stretch exactly one by the tight span construction.

References

^ ^a ^b ^c ^d ^e Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair (2004), "Cuts, trees and $\ell _{1}$ -embeddings of graphs", Combinatorica, 24 (2): 233–269, doi:10.1007/s00493-004-0015-x, MR 2071334
^ Avis, David; Deza, Michel (1991), "The cut cone, $L^{1}$ embeddability, complexity, and multicommodity flows", Networks, 21 (6): 595–617, doi:10.1002/net.3230210602, MR 1128272
^ Linial, Nathan; London, Eran; Rabinovich, Yuri (1995), "The geometry of graphs and some of its algorithmic applications", Combinatorica, 15 (2): 215–245, doi:10.1007/BF01200757, MR 1337355
^ Bourgain, J. (1985), "On Lipschitz embedding of finite metric spaces in Hilbert space", Israel Journal of Mathematics, 52 (1–2): 46–52, doi:10.1007/BF02776078, MR 0815600
^ Leighton, Tom; Rao, Satish (1999), "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms", Journal of the ACM, 46 (6): 787–832, doi:10.1145/331524.331526, MR 1753034
^ Rao, Satish (1999), "Small distortion and volume preserving embeddings for planar and Euclidean metrics", Proceedings of the Fifteenth Annual Symposium on Computational Geometry (SoCG '99), New York: ACM, pp. 300–306, doi:10.1145/304893.304983, ISBN 1-58113-068-6, MR 1802217
^ Lee, James R.; Sidiropoulos, Anastasios (2013), "Pathwidth, trees, and random embeddings", Combinatorica, 33 (3): 349–374, arXiv:0910.1409, doi:10.1007/s00493-013-2685-8, MR 3144806
^ Lee, James R.; Poore, Daniel E. (2013), "On the 2-sum embedding conjecture", Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry (SoCG '13), New York: ACM, pp. 197–206, doi:10.1145/2462356.2492436, ISBN 978-1-4503-2031-3, MR 3208212
^ Chekuri, Chandra; Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair (2006), "Embedding $k$ -outerplanar graphs into $\ell _{1}$ ", SIAM Journal on Discrete Mathematics, 20 (1): 119–136, doi:10.1137/S0895480102417379, MR 2257250

[gnrs-1] Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair (2004), "Cuts, trees and $\ell _{1}$ -embeddings of graphs", Combinatorica, 24 (2): 233–269, doi:10.1007/s00493-004-0015-x, MR 2071334

[ad-2] Avis, David; Deza, Michel (1991), "The cut cone, $L^{1}$ embeddability, complexity, and multicommodity flows", Networks, 21 (6): 595–617, doi:10.1002/net.3230210602, MR 1128272

[llr-3] Linial, Nathan; London, Eran; Rabinovich, Yuri (1995), "The geometry of graphs and some of its algorithmic applications", Combinatorica, 15 (2): 215–245, doi:10.1007/BF01200757, MR 1337355

[b-4] Bourgain, J. (1985), "On Lipschitz embedding of finite metric spaces in Hilbert space", Israel Journal of Mathematics, 52 (1–2): 46–52, doi:10.1007/BF02776078, MR 0815600

[lr-5] Leighton, Tom; Rao, Satish (1999), "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms", Journal of the ACM, 46 (6): 787–832, doi:10.1145/331524.331526, MR 1753034

[r-6] Rao, Satish (1999), "Small distortion and volume preserving embeddings for planar and Euclidean metrics", Proceedings of the Fifteenth Annual Symposium on Computational Geometry (SoCG '99), New York: ACM, pp. 300–306, doi:10.1145/304893.304983, ISBN 1-58113-068-6, MR 1802217

[ls-7] Lee, James R.; Sidiropoulos, Anastasios (2013), "Pathwidth, trees, and random embeddings", Combinatorica, 33 (3): 349–374, arXiv:0910.1409, doi:10.1007/s00493-013-2685-8, MR 3144806

[lp-8] Lee, James R.; Poore, Daniel E. (2013), "On the 2-sum embedding conjecture", Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry (SoCG '13), New York: ACM, pp. 197–206, doi:10.1145/2462356.2492436, ISBN 978-1-4503-2031-3, MR 3208212

[cgnrs-9] Chekuri, Chandra; Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair (2006), "Embedding $k$ -outerplanar graphs into $\ell _{1}$ ", SIAM Journal on Discrete Mathematics, 20 (1): 119–136, doi:10.1137/S0895480102417379, MR 2257250

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Formulation

Related results

See also

References