Goddyn's conjecture on thin spanning trees

From Egres Open
Jump to: navigation, search

A spanning tree of a graph G is called [math]\epsilon[/math]-thin if it contains at most an [math]\epsilon[/math] fraction of the edges of each cut. Is there a function [math]f: (0,1)\to {\mathbb Z}_+[/math] such that every [math]f(\epsilon)[/math]-edge-connected graph has an [math]\epsilon[/math]-thin spanning tree?


This is a conjecture of Goddyn [1] that is a stronger version of the [math](2+\epsilon)[/math]-flow conjecture (Open Problem Garden). If it was true for [math]f(x)=2/x-2[/math], then it would imply Jaeger's modular orientation conjecture (Open Problem Garden). Another consequence concerns the Asymmetric Traveling Salesman Problem. If the conjecture was true for some [math]f(x)=O(1/x)[/math], and the thin spanning tree could be found in polynomial time, then ATSP would have a constant factor approximation algorithm [2][3].

It was shown by Oveis Gharan and Saberi [3] that the conjecture is true for graphs of bounded orientable genus. Erickson and Sidiropoulos [4] proved the existence of thin spanning forests with few components in graphs of bounded genus, and used these to obtain an [math]O(\log(g)/\log\log(g))[/math]-approximation for ATSP. Anari and Oveis Gharan [5] proved that a k-edge-connected graph with [math]k \geq 7 \log(n)[/math] has a [math](\mathrm{polylog}(k)/k)[/math]-thin spanning tree.

The notion of [math]\epsilon[/math]-thinness canbe defined similarly for arbitrary edge sets, not just spanning trees. The following theorem follows from the work of Batson, Spielman and Srivastava [6] on spectral sparsifiers.

Theorem. Given an arbitrary graph [math]G=(V,E)[/math], there exists an edge set [math]F \subseteq E[/math] of size [math]|V|[/math] that is [math]4|V|/|E|[/math]-thin in G.

Related conjectures


  1. L. Goddyn, Some Open Problems I Like
  2. A. Asadpour, M. X. Goemans, A. Madry, S. Oveis Gharan, A. Saberi, An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem, Author link, MIT Open Access
  3. 3.0 3.1 S. Oveis Gharan, A. Saberi, The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus, arXiv link
  4. J. Erickson, A. Sidiropoulos, A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs, arXiv link
  5. N. Anari, S. Oveis Gharan, Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP, arXiv link
  6. J. Batson, D.A. Spielman, N. Srivastava, Twice-Ramanujan Sparsifiers, arXiv link, DOI link