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 An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...

of multi-commodity flow problems. It is named after Anupam Gupta, Ilan Newman, Yuri Rabinovich, and

Alistair Sinclair :' Alistair Sinclair (born 1960) is a British computer scientist and computational theorist. Sinclair received his B.A. in mathematics from St. John’s College, Cambridge in 1979, and his Ph.D. in computer science from the University of Edinbu ...

, who formulated it in 2004.

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

d,Cd /math> 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.

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 graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s are closed under minors. Therefore, it would follow from the GNRS conjecture that the planar graphs have bounded distortion. 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. Therefore, the GNRS conjecture can be rephrased as stating that the minor-closed families of graphs have bounded flow-cut gap.

Related results

Arbitrary

n

-vertex graphs (indeed, arbitrary

n

-point metric spaces) have

\ell_1

embeddings with distortion

O(\log n)

. 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. Therefore, this logarithmic bound on the distortion of arbitrary graphs is tight.

Planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s can be embedded with smaller distortion,

O(\sqrt)

. 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, the graphs of bounded pathwidth, the 2-clique-sums of graphs of bounded size, and the

k

-outerplanar graphs. 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

{{reflist, refs= {{citation , last1 = Avis , first1 = David , author1-link = David Avis , last2 = Deza , first2 = Michel , author2-link = Michel Deza , doi = 10.1002/net.3230210602 , issue = 6 , journal = Networks , mr = 1128272 , pages = 595–617 , title = The cut cone,

L^1

embeddability, complexity, and multicommodity flows , volume = 21 , year = 1991 {{citation , last = Bourgain , first = J. , authorlink = Jean Bourgain , doi = 10.1007/BF02776078 , doi-access=free , issue = 1–2 , journal =

Israel Journal of Mathematics '' Israel Journal of Mathematics'' is a peer-reviewed mathematics journal published by the Hebrew University of Jerusalem (Magnes Press). Founded in 1963, as a continuation of the ''Bulletin of the Research Council of Israel'' (Section F), the jou ...

, mr = 815600 , pages = 46–52 , title = On Lipschitz embedding of finite metric spaces in Hilbert space , volume = 52 , year = 1985 {{citation , last1 = Chekuri , first1 = Chandra , last2 = Gupta , first2 = Anupam , last3 = Newman , first3 = Ilan , last4 = Rabinovich , first4 = Yuri , last5 = Sinclair , first5 = Alistair , author5-link = Alistair Sinclair , doi = 10.1137/S0895480102417379 , issue = 1 , journal = SIAM Journal on Discrete Mathematics , mr = 2257250 , pages = 119–136 , title = Embedding

k

-outerplanar graphs into

\ell_1

, volume = 20 , year = 2006 {{citation , last1 = Gupta , first1 = Anupam , last2 = Newman , first2 = Ilan , last3 = Rabinovich , first3 = Yuri , last4 = Sinclair , first4 = Alistair , author4-link = Alistair Sinclair , doi = 10.1007/s00493-004-0015-x , doi-access=free , issue = 2 , journal = Combinatorica , mr = 2071334 , pages = 233–269 , title = Cuts, trees and

\ell_1

-embeddings of graphs , volume = 24 , year = 2004 {{citation , last1 = Linial , first1 = Nathan , author1-link = Nati Linial , last2 = London , first2 = Eran , last3 = Rabinovich , first3 = Yuri , doi = 10.1007/BF01200757 , doi-access=free , issue = 2 , journal = Combinatorica , mr = 1337355 , pages = 215–245 , title = The geometry of graphs and some of its algorithmic applications , volume = 15 , year = 1995 {{citation , last1 = Lee , first1 = James R. , last2 = Poore , first2 = Daniel E. , contribution = On the 2-sum embedding conjecture , doi = 10.1145/2462356.2492436 , mr = 3208212 , pages = 197–206 , publisher = ACM , location = New York , title = Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry (SoCG '13) , year = 2013 {{citation , last1 = Leighton , first1 = Tom , author1-link = F. Thomson Leighton , last2 = Rao , first2 = Satish , doi = 10.1145/331524.331526 , issue = 6 , journal = Journal of the ACM , mr = 1753034 , pages = 787–832 , title = Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms , volume = 46 , year = 1999 {{citation , last1 = Lee , first1 = James R. , last2 = Sidiropoulos , first2 = Anastasios , doi = 10.1007/s00493-013-2685-8 , issue = 3 , journal = Combinatorica , mr = 3144806 , pages = 349–374 , title = Pathwidth, trees, and random embeddings , volume = 33 , year = 2013, arxiv = 0910.1409 {{citation , last = Rao , first = Satish , contribution = Small distortion and volume preserving embeddings for planar and Euclidean metrics , doi = 10.1145/304893.304983 , mr = 1802217 , pages = 300–306 , publisher = ACM , location = New York , title = Proceedings of the Fifteenth Annual Symposium on Computational Geometry (SoCG '99) , year = 1999, doi-access = free Approximation algorithms Conjectures Unsolved problems in graph theory Graph minor theory Metric geometry

Formulation

Related results

See also

References