Goddyn's conjecture on thin spanning trees
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?
Remarks
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
- Smooth well-balanced orientations with prescribed in-degrees
- Sparsifier subgraphs
- [math](2+\epsilon)[/math]-flow conjecture (Open Problem Garden)
- Jaeger's modular orientation conjecture (Open Problem Garden)
- Mapping planar graphs to odd cycles (Open Problem Garden)
References
- ↑ L. Goddyn, Some Open Problems I Like
- ↑ 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.0 3.1 S. Oveis Gharan, A. Saberi, The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus, arXiv link
- ↑ J. Erickson, A. Sidiropoulos, A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs, arXiv link
- ↑ N. Anari, S. Oveis Gharan, Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP, arXiv link
- ↑ J. Batson, D.A. Spielman, N. Srivastava, Twice-Ramanujan Sparsifiers, arXiv link, DOI link
