A spanning tree that stays thin across every cut

← All digests

Family 174 · Combinatorics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

A connected network can be reduced to a spanning tree: a connected backbone with no cycles and only one fewer edge than vertices. But the backbone may concentrate heavily across some division of the network. Can one choose a tree that uses only a small fraction of the original connections across every division simultaneously?

If every cut has at least $k$ edges, the strong thin-tree conjecture asks for a tree using at most a universal constant times $1/k$ of each cut. The constant must be independent of the network’s size.

The first manuscript claims this existence theorem for all finite loopless multigraphs. The second claims a deterministic polynomial-time construction, even when enormous bundles of parallel edges are represented compactly by binary integers. It also obtains a tree whose total cost and all cut loads are simultaneously controlled by fractional input data.

2. Background and essential definitions

A multigraph may have several separate edges joining the same pair of vertices. Here edges are undirected, and loops from a vertex to itself are excluded in the main theorem. Parallel copies count separately.

For a subset $S$ of the vertex set, the cut $\delta_G(S)$ consists of edges with exactly one endpoint in $S$. A graph is $k$-edge-connected when

$$|\delta_G(S)|\geq k$$

for every nonempty proper subset $S$. Thus deleting fewer than $k$ edges cannot disconnect it.

A spanning tree $T$ uses all vertices, remains connected, and contains no cycle. It is $\alpha$-thin in $G$ if

$$|\delta_T(S)|\leq\alpha|\delta_G(S)|$$

for every nontrivial cut. This is a simultaneous condition on exponentially many possible vertex subsets. It is much stronger than merely asking the tree to have few edges in total.

The scale $1/k$ cannot be improved in general. Take two vertices joined by $k$ parallel edges. Every spanning tree consists of one edge, so it uses exactly a $1/k$ fraction of the unique cut. The question is whether every highly connected multigraph admits this optimal scale up to a fixed factor.

A collection of edge-disjoint spanning trees is called a tree packing. Distinct trees in the packing share vertices but no edge copies. Classical packing theorems supply many such trees when edge connectivity is large, providing a starting resource for the new argument.

3. Development history and previous partial results

Goddyn’s thin-tree conjecture asks whether any prescribed positive thinness can be achieved by requiring sufficiently high edge connectivity. The strong version asks for the quantitative rate $C/k$, with one universal constant $C$.

Thin trees became important in approximation algorithms for the asymmetric traveling salesman problem, where travel costs depend on direction. Asadpour, Goemans, Mądry, Oveis Gharan and Saberi used probability distributions on spanning trees to obtain an approximation ratio of order $\log n/\log\log n$. The same approach gives thin trees with a size-dependent loss over the inverse-connectivity scale.

Geometric restrictions made the conjectured rate accessible earlier. Oveis Gharan and Saberi established inverse-connectivity bounds for planar graphs and, with surface-dependent constants, graphs of bounded orientable genus.

For unrestricted multigraphs, Anari and Oveis Gharan developed effective-resistance-reducing flows and hierarchies of locally connected vertex sets. Their result gives thinness of the form

$$\frac{\operatorname{poly}(\log\log n)}{k},$$

where the numerator is a fixed polynomial in the iterated logarithm of the number of vertices. This was much closer to the desired bound, but still not independent of $n$.

More recent work handled structured collections of cuts. Klein and Olver treated prescribed laminar families, whose sets are nested or disjoint. Klein, Olver and Yeoh controlled all cuts sufficiently close to the minimum size. The present claim removes both the restriction on which cuts are controlled and the dependence on graph order.

Constant-factor approximation for asymmetric traveling salesman was already obtained by Svensson, Tarnawski and Végh, then improved by Traub and Vygen. Accordingly, these manuscripts present thin trees as a structural and rounding advance, rather than the first constant-factor algorithm for that traveling salesman problem.

4. What the new manuscripts claim

Existence and construction

Manuscript M1 states that there is a universal constant $C>0$ such that every finite loopless $k$-edge-connected multigraph with at least two vertices has a spanning tree satisfying

$$|\delta_T(S)|\leq\frac{C}{k}|\delta_G(S)| \qquad(\varnothing\ne S\subsetneq V(G)).$$

Manuscript M2 claims a deterministic algorithm producing such a tree in time polynomial in the total binary input length. It permits either an explicit list of edge copies or a list of endpoint pairs with multiplicities written in binary. The one-vertex case returns the empty tree.

The binary guarantee is substantive. A multiplicity represented by a short integer may stand for exponentially many edge copies. An algorithm polynomial in the expanded number of copies would not meet the stated bound.

Simultaneously thin and inexpensive

M2 also treats nonnegative rational edge masses $x_e$ and costs $c_e$, given in binary, with

$$x(\delta_G(S))=\sum_{e\in\delta_G(S)}x_e\geq1$$

for every nontrivial cut. For an absolute constant $A$, it claims a polynomial-time construction of a tree using only edges with $x_e>0$, satisfying

$$|\delta_T(S)|\leq A x(\delta_G(S))$$

for all cuts and

$$\sum_{e\in T}c_e\leq A\sum_{e\in E(G)}c_ex_e.$$

The same tree obeys both requirements. The costs need not form a metric or satisfy triangle inequalities. This corollary even allows loops in the input records; they are discarded because they help no cut and have nonnegative cost.

5. Why the advance matters

Importance: 5/5. The strong thin-tree conjecture is a central question connecting connectivity, graph sparsification and optimization. The claimed result reaches the necessary inverse-connectivity scale for all cuts at once, and the companion turns that statement into a finite-bit algorithm.

A tree packing alone does not solve the problem. For each fixed cut, averaging over the packed trees finds some tree with low load on that cut. But the favorable tree may change when the cut changes. The theorem must select one tree that works for all of them.

The cost-and-cut consequence is valuable for rounding: a fractional solution spreads resources over many edges, while an actual network must make discrete choices. The claim says that both global expense and every connectivity boundary can survive this conversion with universal losses. The combination of optimal scale, unrestricted graphs and constructive control motivates the highest rating.

6. The main idea

Keep connectivity while repeatedly thinning

Start with many edge-disjoint spanning trees, supplied by the Nash–Williams–Tutte packing theorem. The manuscripts repeatedly select smaller edge sets. Each step should reduce the size of every cut by roughly one half while retaining roughly half as many packed spanning trees.

If these two quantities shrink together, their ratio stays controlled. After enough steps, the remaining graph still contains a spanning tree, while its cut sizes are small compared with those of the original graph. Any surviving tree inherits that cut bound.

The challenge is preventing the small relative losses at each step from accumulating into a factor depending on the number of vertices. The papers arrange losses that become sufficiently small when the packing is large, so their product over the iteration stays universally bounded.

Use two matrix descriptions of the same edges

For an edge $e=uv$, let $b_e$ be the vector with a one at $u$, a minus one at $v$, and zeros elsewhere. The graph Laplacian is

$$L_G=\sum_e b_eb_e^T.$$

If $\mathbf1_S$ is the indicator vector of a vertex subset, then

$$\mathbf1_S^T L_G\mathbf1_S=|\delta_G(S)|.$$

Thus one matrix encodes all cut sizes. A suitable positive quadratic form also assigns edges an effective-resistance quantity, measuring how costly an edge direction is relative to that form. The hierarchy argument extracts a large packing using edges of small resistance.

A second vector representation records information needed for tree packing. Controlling only the first matrix would be insufficient: a single edge of weight $q$ has the same Laplacian as $q$ parallel unit edges, but only the latter can supply $q$ edge-disjoint trees. The proof must preserve actual edge copies and the relevant rank constraints.

The two representations are stacked together. A matrix partition theorem then chooses one edge subset that controls both systems. This is how spectral estimates and combinatorial connectivity are kept synchronized.

Make the existence argument computational

M1 uses geometric and fixed-point arguments to obtain the required matrices. M2 replaces those steps with finite convex optimization, rational approximations with certified error bounds, and a constructive matrix-signing method.

It also compresses binary multiplicities before expanding edges. This avoids spending time proportional to an exponentially large number of copies. The final selected tree is then translated back to original edge records. These are additional algorithmic ingredients; the polynomial-time guarantee does not follow merely from the existence proof.

7. Scope, limitations, and open questions

The main result concerns undirected loopless multigraphs with a promised edge-connectivity parameter. It does not state an analogous theorem for directed spanning structures. The arbitrary orientation used to define $b_e$ is only matrix notation; it does not turn the graph into a directed input.

The constants are universal but are not presented as optimized practical values. For small $k$, the bound $C/k$ can exceed one and become uninformative beyond ordinary connectivity. Its force is the rate as connectivity grows.

M2’s complexity guarantee uses finite rational and integer encodings. It is not a claim about arbitrary real numbers supplied by an exact-value oracle. Nor does polynomial running time imply that the construction is immediately competitive for large practical networks.

Finally, cut thinness should not be silently replaced by a stronger spectral comparison against the original Laplacian on every real vector. The stated output guarantee concerns cuts, with additional matrix machinery used internally to achieve it.

8. Sources and further reading

M1 contains the existence theorem, the hierarchy argument and the packing-preserving iteration. M2 develops the finite-bit construction and the simultaneous cost-and-cut rounding corollary.

Primary predecessors include Anari–Oveis Gharan on resistance-reducing flows, Oveis Gharan–Saberi on bounded-genus graphs, and Harvey–Olver on matrix rounding. The manuscripts’ bibliographies identify the classical spanning-tree packing theorems, the Marcus–Spielman–Srivastava partition theorem, and the constructive signing method used by M2.

Source manuscripts

• M1. OpenAI, The strong thin tree conjecture (September 23, 2026).
• M2. OpenAI, A polynomial-time construction of strong thin trees (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.