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 ℓ 1 {\displaystyle \ell _{1}} \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 {\displaystyle d} d to pairs of vectors with distance in the range \( {\displaystyle [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 nontrivial minor-closed family of 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.
See also
Partial cube, a class of graphs with distortion-free unweighted \( \ell _{1} \)-embeddings
References
Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair (2004), "Cuts, trees and ℓ 1 {\displaystyle \ell _{1}} \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 {\displaystyle L^{1}} 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, 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, MR 3208212
Chekuri, Chandra; Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair (2006), "Embedding k {\displaystyle k} k-outerplanar graphs into ℓ 1 {\displaystyle \ell _{1}} \ell _{1}", SIAM Journal on Discrete Mathematics, 20 (1): 119–136, doi:10.1137/S0895480102417379, MR 2257250
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
