# 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