Nathan Klein

Nathan Klein, Neil Olver, Zi Song Yeoh

The strong thin tree conjecture states that every $k$-edge-connected graph $G$ contains an $O(1/k)$-thin spanning tree, meaning a spanning tree which contains at most an $O(1/k)$ fraction of the edges across each cut in $G$. This conjecture is still open despite significant effort; the best current result by Anari and Oveis Gharan shows the existence of an $O(\text{polyloglog}(n)/k)$-thin tree. In this work, we demonstrate that the conjecture is true if one only requires thinness for the set of $η$-near minimum cuts of the graph for $η= 1/40$, in other words, for the set of cuts with fewer than $(1+1/40)k$ edges. Our approach constructs such a tree in polynomial time. To show this, we utilize the structure of near minimum cuts, and in particular the polygon representation of Benczúr and Goemans, to reduce to the previously solved problem of finding a spanning tree that is $O(1/k)$-thin for all sets in a laminar family.

Vincent Cohen-Addad, Marina Drygala, Nathan Klein et al.

The Weighted Tree Augmentation Problem (WTAP) is a fundamental network design problem where the goal is to find a minimum-cost set of additional edges (links) to make an input tree 2-edge-connected. While a 2-approximation is standard and the integrality gap of the classic Cut LP relaxation is known to be at least 1.5, achieving approximation factors significantly below 2 has proven challenging. Recent advances of Traub and Zenklusen using local search culminated in a ratio of $1.5+ε$, establishing the state-of-the-art. In this work, we present a randomized approximation algorithm for WTAP with an approximation ratio below 1.49. Our approach is based on designing and rounding a strong linear programming relaxation for WTAP which incorporates variables that represent subsets of edges and the links used to cover them, inspired by lift-and-project methods like Sherali-Adams.