Goddyn's conjecture on thin spanning trees

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

Remarks

This is a conjecture of Goddyn that is a stronger version of the $$(2+\epsilon)$$ -flow conjecture (Open Problem Garden). If it was true for $$f(x)=2/x-2$$ , 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 $$f(x)=O(1/x)$$ , and the thin spanning tree could be found in polynomial time, then ATSP would have a constant factor approximation algorithm .

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

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

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

Related conjectures

• Smooth well-balanced orientations with prescribed in-degrees
• Sparsifier subgraphs
• $$(2+\epsilon)$$ -flow conjecture (Open Problem Garden)
• Jaeger's modular orientation conjecture (Open Problem Garden)
• Mapping planar graphs to odd cycles (Open Problem Garden)