theoretical computer science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...

and

metric geometry In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...

, the GNRS conjecture connects the theory of

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

s, the

stretch factor The stretch factor (i.e., bilipschitz constant) of an embedding measures the factor by which the embedding distorts distances. Suppose that one metric space is embedded into another metric space by a metric map, a continuous one-to-one functi ...

embedding In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object X is said to be embedded in another object Y, the embedding is g ...

s, 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 ' ...

multi-commodity flow problem The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes. Definition Given a flow network \,G(V,E), where edge (u,v) \in E has capacity \,c(u,v). There are \,k comm ...

s. 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 graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

s into

\ell_1

spaces, real

vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...

s 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

or distortion is the ratio

C/c

; an

isometry In mathematics, an isometry (or congruence, or congruent transformation) is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος ''isos'' me ...

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

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. An alternative formulation involves analogues of the

max-flow min-cut theorem In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the ''source'' to the ''sink'' is equal to the total weight of the edges in a minimum cut, i.e., the ...

for undirected

s. 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 space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...

s) 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 In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applica ...

. Therefore, this logarithmic bound on the distortion of arbitrary graphs is tight. Planar graphs 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 graph In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits. Definition and t ...

s and the graphs of bounded

circuit rank In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or fo ...

, the graphs of bounded

pathwidth In graph theory, a path decomposition of a graph is, informally, a representation of as a "thickened" path graph, and the pathwidth of is a number that measures how much the path was thickened to form . More formally, a path-decomposition ...

, 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 In mathematics, the Johnson–Lindenstrauss lemma is a result named after William B. Johnson and Joram Lindenstrauss concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. The lemma states that a ...

, and into

\ell_\infty

spaces with stretch exactly one by the

tight span In metric geometry, the metric envelope or tight span of a metric space ''M'' is an injective metric space into which ''M'' can be embedded. In some sense it consists of all points "between" the points of ''M'', analogous to the convex hull of a ...

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 , 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 '' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was estab ...

, 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 ''Combinatorica'' is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honora ...

, 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 =

, 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 The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is Venkatesan ...

, 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 =

, 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