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(polylog log 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.

This paper investigates the energy complexity of several well-studied (local) problems in distributed graph algorithms—namely, matching and vertex cover approximations, spanners, low-outdegree orientations, and set cover. We present randomized distributed algorithms that, while having round complexity almost matching the respective state of the art, achieve nearly exponentially smaller energy complexity. That is, in each of these algorithms, each node is awake for only an exponentially small fraction of the time, and the round complexity still remains almost the same as the best-known algorithm. During the rest of the rounds, the node does not perform any computation or communication (and any messages sent to it at that time go unheard).