L1 Embeddings of Graphs of Bounded TreewidthResearch Paper
Motivation: embeddings, sparsest cut and the GNRS conjecture
A finite metric embeds into exactly when it is a nonnegative combination of cut metrics . This makes distortion the right measure for the flow–cut gap: given edge capacities and pairwise demands, the ratio between the sparsest cut value and the maximum concurrent flow . Linial, London and Rabinovich (1995) and Aumann and Rabani (1998) developed this connection, and Gupta, Newman, Rabinovich and Sinclair (2004) proved that the worst flow–cut gap on a fixed graph equals the worst distortion of its weighted shortest-path metrics. They conjectured that every proper minor-closed family embeds into with uniformly bounded distortion (the GNRS conjecture). Graphs of bounded treewidth form one of its basic cases.
Timeline
- 1986 — Robertson and Seymour: excluding a fixed planar graph as a minor bounds the treewidth (JCTB 1986).
- 2004 — Gupta, Newman, Rabinovich and Sinclair prove the treewidth-two (series-parallel) case, show that some series-parallel metrics need expected tree distortion , and state the GNRS conjecture (Combinatorica 2004).
- 2006 — Chekuri, Gupta, Newman, Rabinovich and Sinclair: bounded distortion for -outerplanar graphs (SIDMA 2006).
- 2008–2010 — Chakrabarti, Jaffe, Lee and Vincent obtain the optimal bound for treewidth two (FOCS 2008), matched by Lee and Raghavendra (DCG 2010).
- 2010 — Chlamtáč, Krauthgamer and Raghavendra: bounded distortion for bounded treewidth under a local-consistency assumption on small vertex sets (APPROX/RANDOM 2010).
- 2013 — Lee and Sidiropoulos settle bounded pathwidth via stochastic tree embeddings (Combinatorica 2013); Lee and Poore treat 2-sums of a fixed finite family (SoCG 2013).
- 2022 — Abraham, Filtser, Gupta and Neiman: distortion for pathwidth (SICOMP 2022).
- 2025 — Filtser et al.: optimal padded decompositions for bounded treewidth and an bound (TheoretiCS 2025).
- 2026 — An OpenAI preprint, Embeddings of Graphs of Bounded Treewidth (OpenAI Math Release, September 23, 2026), claims a uniform bound for every fixed treewidth. The preprint has not been peer reviewed, and its main theorem is not formally verified.
Setting
Let be a finite connected graph with edge lengths . The shortest-path metric is the least total length of a path from to .
A tree decomposition of is a finite tree with bags () such that the bags cover , each edge has both endpoints in some bag, and for each vertex the nodes whose bag contains induce a connected subtree. In this mission, as in the source, bounds the bag cardinality , so the treewidth bound is .
A map has distortion at most if .
Formalization targets
Goal: Theorem 1.1 (bounded-treewidth graph metrics in )
For every integer there is a constant such that for every nonempty finite connected graph with a tree decomposition of bag size at most and every , there are and with
is independent of the number of vertices, the decomposition and all ratios of edge lengths; the goal asserts only its existence. The goal statement is published on the platform with status Open: no machine-checked proof exists yet.
Significance
The result itself. The theorem settles the bounded-treewidth case of the GNRS conjecture. Through the GNRS equivalence, it gives for every multicommodity instance on graphs of treewidth less than . By the Robertson–Seymour excluded-planar-minor theorem it also covers every family excluding a fixed planar minor. Combined with known approximation algorithms for the minimum distortion (Gupta–Talwar–Witmer 2013; Cohen-Addad–Mömke–Verdugo 2024), it yields fixed-parameter-time embeddings of distortion . With the planar companion preprint it covers the almost-embeddable families of Lee and Sidiropoulos.
Formalizing it. The proof constructs cut measures directly on a tree decomposition and combines them with padded random partitions from the literature. A formal proof would certify that the constants depend only on , the point at which earlier approaches lost uniformity.
Difficulty
The successful pathwidth approach embeds the graph stochastically into dominating trees, but that route cannot work here: some series-parallel metrics require expected tree distortion (GNRS 2004, Theorem 5.6). Local-consistency approaches assume that small vertex sets admit compatible isometric cut representations, which a general bounded-treewidth metric need not provide. Multiscale constructions from padded partitions give good separation at each scale, but summing their contributions loses a factor growing with the number of scales. The construction must handle arbitrary branching of the decomposition tree and arbitrary edge-length ratios without such accumulation.
Formalization scope
- The vertex type
Vis any nonemptyFintypewith decidable equality;G : SimpleGraph Vis connected. HasTreeDecomposition G k: a treeTonFin n, bagsFin n → Finset Vcovering all vertices and all edges, with the bags containing each vertex inducing a connected subgraph ofT, and all bags of cardinality at mostk.- Edge lengths are
ℓ : G.edgeSet → ℝ, strictly positive.shortestPathDistanceis thesInfof lengths of paths (IsPath) from to ; this set is finite and nonempty for a connected finite graph, so the infimum is the true distance. - The target is the finite-dimensional space
PiLp 1 (Fin m → ℝ)with chosen per graph; this is the source's remark (p. 2) that the target can be taken to be finite-dimensional , and it is at least as strong as an target. - The constant
Cdepends only onkand is quantified before the graph. - Infrastructure needed: tree decompositions, cut-measure representations of metrics, Markov flows on layered graphs, padded decompositions. Tree-decomposition and cut-metric infrastructure is reusable.
Selected references
- N. Robertson, P. D. Seymour, Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B 41 (1986), 92–114. https://doi.org/10.1016/0095-8956(86)90030-4
- N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), 215–245. https://doi.org/10.1007/BF01200757
- Y. Aumann, Y. Rabani, An approximate min-cut max-flow theorem and approximation algorithm, SIAM J. Comput. 27 (1998), 291–301. https://doi.org/10.1137/S0097539794285983
- A. Gupta, I. Newman, Y. Rabinovich, A. Sinclair, Cuts, trees and -embeddings of graphs, Combinatorica 24 (2004), 233–269. https://doi.org/10.1007/s00493-004-0015-x
- A. Chakrabarti, A. Jaffe, J. R. Lee, J. Vincent, Embeddings of topological graphs: lossy invariants, linearization, and 2-sums, FOCS 2008, 761–770. https://doi.org/10.1109/FOCS.2008.79
- J. R. Lee, P. Raghavendra, Coarse differentiation and multi-flows in planar graphs, Discrete Comput. Geom. 43 (2010), 346–362. https://doi.org/10.1007/s00454-009-9172-4
- E. Chlamtáč, R. Krauthgamer, P. Raghavendra, Approximating sparsest cut in graphs of bounded treewidth, APPROX/RANDOM 2010, LNCS 6302, 124–137. https://doi.org/10.1007/978-3-642-15369-3_10
- J. R. Lee, A. Sidiropoulos, Pathwidth, trees, and random embeddings, Combinatorica 33 (2013), 349–374. https://doi.org/10.1007/s00493-013-2685-8
- I. Abraham, A. Filtser, A. Gupta, O. Neiman, Metric embedding via shortest path decompositions, SIAM J. Comput. 51 (2022), 290–314. https://doi.org/10.1137/19M1296021
- A. Filtser, T. Friedrich, D. Issac, N. Kumar, H. Le, N. Mallek, Z. Zeif, Optimal padded decomposition for bounded treewidth graphs, TheoretiCS 4 (2025), Article 22. https://doi.org/10.46298/theoretics.25.22
- OpenAI, Embeddings of Graphs of Bounded Treewidth, OpenAI Math Release preprint, September 23, 2026 (source of the goal; Theorem 1.1, p. 2). https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/L1-Embeddings-of-Graphs-of-Bounded-Treewidth-September-23-2026/paper.pdf