1 Introduction
A spanning tree retains connectivity with only n-1 edges. A thin spanning tree must also use a small fraction of every cut, with the same tree serving all cuts simultaneously. We give a deterministic polynomial-bit construction at the inverse-connectivity scale.
Throughout, graphs are finite undirected loopless multigraphs, and every parallel copy counts separately. For S\subseteq V(G), let \delta_G(S) be the multiset of edges with one endpoint in S and the other in its complement. The graph is k-edge-connected if |\delta_G(S)|\ge k for every nonempty proper S. A spanning tree T is \alpha-thin in G if
We consider two input representations: an explicit list of labelled edge copies, or a list of endpoint pairs with nonnegative integer multiplicities written in binary. In the second representation, the number of edge copies may be exponential in the input length.
Theorem 1.1 (Algorithmic strong thin trees). There is an absolute constant C with the following property. Given a finite k-edge-connected multigraph G on at least one vertex and an integer k\ge1, a deterministic algorithm returns a spanning tree T satisfying
in time polynomial in the total binary input length, whether edges are listed explicitly or multiplicities are encoded in binary. For a one-vertex graph the answer is the empty tree.
The universal C/k bound is the strong thin-tree conjecture. The companion article The strong thin tree conjecture [20] proves the existence statement and supplies the complete hierarchy geometry used here. Theorem 1.1 gives the positive algorithmic resolution in both finite input models. Its order in k is necessary: for two vertices joined by k parallel edges, the unique cut contains exactly one tree edge.
The construction also gives simultaneous cost-and-cut rounding. Given nonnegative rational edge weights whose mass on every cut is at least one, and any nonnegative rational edge costs, we find a tree in the positive support with every cut load and its total cost bounded by constant multiples of the corresponding fractional quantities (Corollary 7.1). No metric assumption on the costs is needed.
1.1 Context and prior work
Goddyn’s qualitative conjecture asks whether every positive thinness bound follows from sufficiently large edge connectivity, independently of graph order [11, Problem 4]. The strong form specifies the rate C/k; the distinction is made explicitly in [1, Conjecture 1.3 and the following discussion]. One source of algorithmic interest is the asymmetric traveling salesman problem, which asks for a minimum-cost tour through the vertices of a directed metric. Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi used maximum-entropy spanning-tree distributions to obtain an O(\log n/\log\log n) approximation [4]. Their rounding method also gives the constructive O(\log n/(k\log\log n)) thin-tree scale; see [1, Section 1].
For planar graphs, and more generally on each fixed orientable surface, Oveis Gharan and Saberi obtained constructive inverse-connectivity bounds [21, Theorem 5.1]. For general multigraphs, Anari and Oveis Gharan introduced effective-resistance-reducing flows and locally connected hierarchies, and proved the existence of \operatorname{poly}(\log\log n)/k-thin trees [1, Corollary 1.8]. Their geometric method is the principal foundation of the hierarchy argument in the companion and its extension below. The existence theorem does not itself give a polynomial-time construction of those trees.
Recent work has obtained inverse-connectivity bounds for structured families of cuts. Klein and Olver treat every prescribed laminar family [15]. Klein, Olver, and Yeoh construct a tree crossing each cut of size less than (1+1/40)k at most 88 times [16, Theorem 1]. Our conclusion controls all cuts of an arbitrary multigraph. Thin trees remain an independent structural problem: constant-factor approximation for asymmetric traveling salesman was already established by Svensson, Tarnawski, and Végh and subsequently improved by Traub and Vygen [23, 25].
1.2 From the geometric existence proof to an algorithm
High edge connectivity supplies many edge-disjoint spanning trees by the Nash–Williams–Tutte theorem [19, 26]. A packing bounds the average tree load on each fixed cut, but does not identify one tree that is small on every cut. The companion retains a large packing through successive sparsifications, reducing cut sizes and packing size by almost the same factor. Two vector representations allow the same edge subset to preserve cut control and enough rank information to certify all partition inequalities for tree packing. Iterated matrix halving with a bounded product of losses was used by Harvey and Olver to obtain spectrally thin trees under an effective-resistance hypothesis [13, full version, Appendix F]. Here the additional packing representation permits iteration from edge connectivity.
A shortcut matrix is a positive quadratic form that bounds cut sizes; its inverse assigns each edge a resistance, and edges of low resistance are the candidates retained for sparsification. Three steps of the existence argument require new computational work. The shortcut matrix must be consistent with partitions determined by that same matrix; its construction by compactness and a fixed point does not provide a uniform finite search bound. Real whitening may introduce irrational entries, so a polynomial-bit algorithm must specify its numerical data and control every precision loss. Finally, the existential matrix partition theorem of Marcus, Spielman, and Srivastava must be replaced by an algorithm that finds the signs. We use the public constructive method of Ezeunala and Jiang, with a quantitative implementation proved below, while retaining the packing argument.
A larger cone of geometric tests. The companion bounds a shortcut matrix on cut vectors. For optimization we use centered positive semidefinite matrices whose squared distances satisfy triangle inequalities. This cone has polynomially many displayed constraints. Enlarging the cone strengthens the required shortcut inequality, so the companion’s cut-only statement cannot simply be applied. We extend its proof by constructing a doubled distance-profile polytope in which radii about vertex images are affine and radial motion has exactly its metric length. The underlying distance-profile isometry is classical [10, 17]; the additional radial identities make the bag and charging arguments work in the new geometry.
Continuous capacities and finite optimization. Instead of selecting edges abruptly at a resistance threshold, we assign capacities through a continuous ramp. A convex response lowers the resistance cutoff while maintaining the partition inequalities with a controlled loss in packing size. Uncrossing reduces a putative obstruction to a chain of partitions, where the geometric response applies simultaneously. Exact rational separation and a quantitative interior ball turn each response into a finite computation using the ellipsoid method [12]. Constructive graphic matroid partition then recovers an integer packing [8, 24].
Exact data and certified sparsification. A log-determinant normalization, following the variational method behind radial isotropic position [7, Section 2.2], gives the second vector representation. We approximate the stacked vectors rationally, complete their covariance exactly to the identity, and apply constructive matrix signing. This step builds on the Kadison–Singer partition theorem of Marcus, Spielman, and Srivastava [18] and the public rank-one discrepancy method of Ezeunala and Jiang [9]; the exact interface and the constant used are proved in Appendix A. Rational matrix certificates imply every cut and packing estimate needed for the next step. The product of the multiplicative losses remains bounded through the iteration. A separate truncation and rounding reduction handles binary multiplicities before any edge expansion: it produces a graph with polynomially many explicit copies, independently of the numerical values of the multiplicities and k. The final tree lifts to original edge copies.
Organization. Section 2 proves the metric-cone hierarchy estimate and its simultaneous response to a partition chain. Section 3 constructs a rational shortcut and a large packing of low-resistance edges. Section 4 builds the rank-preserving frame. Section 5 provides exact rational padding and signing certificates. Section 6 combines the two representations, iterates the sparsification, and proves the binary-multiplicity reduction. Section 7 records a simultaneous cost-and-cut rounding consequence for rational fractional inputs. Appendix A gives the quantitative rational implementation of the public rank-one signing method.
2 Metric-cone shortcuts for thin trees
We next develop the geometric input to the thin-tree algorithm. The shortcut theorem of the companion [20] tests a matrix on cuts. Convex optimization in the next section will use a larger, finitely described cone of tests. We establish the corresponding hierarchy estimate by extending its complete geometric arguments, which follow the hierarchy and effective-resistance framework of Anari and Oveis Gharan [1, Sections 5–7].
Throughout this section graphs are finite loopless multigraphs on a vertex set V, with n=|V|\ge2; edge sets retain multiplicities. All symmetric matrices act on the Euclidean space \mathsf E=\one^\perp\subset\R^V. Equivalently, they are centered full matrices, with their zero action on \Span\{\one\} understood. Write \Id_{\mathsf E} for the identity on this space, b_{uv}=e_u-e_v, and L_G=\sum_{e\in E(G)}b_eb_e^T, using arbitrary edge orientations. Matrix pairings are {\mathopen{\langle}A,Z\mathclose{\rangle}}=\tr(AZ). Define the closed convex cone
Its trace-dual cone is \mathcal N^*=\{A:{\mathopen{\langle}A,Z\mathclose{\rangle}}\ge0\text{ for all }Z\in\mathcal N\}. The Gram-matrix representation of squared Euclidean distances is classical [22]; the additional triangle inequalities give the standard \ell_2^2 metric relaxation [2, Section 2]. For Z\in\mathcal N, the numbers d(u,v)=b_{uv}^TZb_{uv} form a squared Euclidean pseudometric. The centered identity belongs to \mathcal N. So does c_Sc_S^T, where c_S=\one_S-(|S|/n)\one: its squared distances are precisely the 0–1 cut metric of S.
A hierarchy is a rooted tree of distinct nonempty subsets of V, with root V, singleton leaves, and children partitioning their parent into at least two sets. For a nonroot node A, with parent A^*, set
The hierarchy is locally h-connected if every G[A] is h-edge-connected, with the singleton condition vacuous. Each |O(A)|\ge h. Each graph edge belongs to exactly two parent boundaries: those of the two children of its endpoints’ least common ancestor. In particular its multiplicity in any selected collection of parent boundaries is at most two.
Theorem 2.1 (Hierarchy bound for the metric test cone). There is an absolute integer h_0 such that, for every integer h\ge h_0, every locally h-connected hierarchy of G, and every collection \mathcal M of nonroot nodes satisfying |O(A)|\ge |P(A)|/h, there is a matrix D\succ0 on \mathsf E with
The cutoff is independent of the graph and the hierarchy depth.
The proof first expresses the shortcut objective as a ratio whose denominator is total edge length. We then represent its numerator by collections of disjoint balls and charge their radii to edge lengths; the resulting estimate will give simultaneous responses to partition chains.
2.1 The conic dual
Lemma 2.2 (A geometric upper bound for the shortcut program). Let G be connected and \mathcal M a nonempty finite collection of nonroot nodes with nonempty parent boundaries. Let p_* be the infimum, over D\succ0 satisfying Equation (2.2), of the largest marked average resistance. Then
Here p_v are Euclidean points whose squared distances d(u,v)=\norm{p_u-p_v}_2^2 satisfy the triangle inequalities, the denominator is positive, and U has orthonormal rows u_e^T. The Euclidean dimension may be enlarged.
Proof. Put A_A=|O(A)|^{-1}\sum_{e\in O(A)}b_eb_e^T and f_A(D)=\tr(A_AD^{-1}). These functions are convex, since
The conic constraint is L_G-D\in\mathcal N^*. Choose D_0=\delta\Id_{\mathsf E} with 0<\delta<\lambda_{\min}(L_G|_{\mathsf E}). Then L_G-D_0\succ0 lies in the interior of \mathcal N^*, because the positive semidefinite cone is contained in \mathcal N^*. Taking an epigraph height above all f_A(D_0) makes the other inequalities strict as well.
For completeness, finite-dimensional separation gives the needed strong duality even if the infimum is not attained. Separate (0,0,p_*) from the open convex set of (a,M,z) for which some D\succ0 and t\in\R satisfy
Monotonicity in the three coordinates makes the separating coefficients (\lambda,Z,\gamma) satisfy \lambda\ge0, Z\in\mathcal N, and \gamma\ge0. The strictly feasible point just constructed rules out \gamma=0: one may take all a_A<0 and M in -\operatorname{int}\mathcal N^*, making the pairing strictly negative for every nonzero (\lambda,Z). Normalize \gamma=1. The unrestricted variable t then forces \sum_A\lambda_A=1. Taking limits to the boundary of the open set, and using weak duality for the reverse inequality, gives
For any A,Z\succeq0,
When A,Z\succ0, set H=Z^{1/2}DZ^{1/2} and C=Z^{1/2}AZ^{1/2}. The objective minus 2\tr(C^{1/2}) is \norm{H^{-1/2}C^{1/2}-H^{1/2}}_{\mathrm F}^2, and vanishes at H=C^{1/2}. For singular A or Z, add \eta\Id_{\mathsf E} to both. The positive definite identity at each fixed D, followed by \eta\downarrow0, proves the lower bound. The unperturbed infimum is at most the perturbed infimum, whose limit gives the upper bound. These are auxiliary perturbations for the identity, not extra dual feasibility assumptions.
For Z\ne0 in \mathcal N, connectivity gives \mathcal E=\tr(L_GZ)>0. Writing N_0=\tr((Z^{1/2}A(\lambda)Z^{1/2})^{1/2}), optimization over the scale \tau Z gives
The zero multiplier contributes zero. Represent Z as the centered Gram matrix of points p_v, and put
Then N_0 is the nuclear norm of the matrix with columns \sqrt{w_e}(p_u-p_v). The singular value decomposition, after adding zero coordinates if needed, gives
Changing individual row signs preserves row orthonormality, so take the displayed contributions nonnegative. For such a maximizing U,
The first line uses \sqrt{\sum_jx_j}\le\sum_j\sqrt{x_j} and the second uses \sum_A\lambda_A=1. Overlapping boundaries are allowed. Substitution into Equation (2.5) proves the claim.
2.2 A convex realization with exact radial motion
Starting from the classical distance-profile isometry into \ell_\infty [10, 17], we construct a continuous geometry for an arbitrary finite metric. It will be used for balls and shells; the Euclidean points p_v remain the inputs to the spectral argument. Figure 1 contrasts the Euclidean spectral points with the distance-profile realization of the same vertex labels and illustrates the exact radial motion of Lemma 2.3.
Lemma 2.3 (Doubled distance profiles). Every finite metric (S,d) has an isometric realization x\mapsto c_x in a convex polytope Q in a finite-dimensional normed space with the following properties. Distance \rho_x(q)=\norm{q-c_x} is affine on Q. There is a common R>0 and a point c_x^-\in Q such that
From any q\in Q one can reach every radial value in [0,R] by moving toward c_x or c_x^-, and the change in radius equals the distance moved. Every straight segment in Q has its norm length, and clamped radial functions are piecewise affine on it.
Proof. Take R>2\max_{x,y}d(x,y) and two copies x^+,x^- of each point. On the doubled set define
This is a metric. A triangle with all signs equal is an original triangle. A triangle with two equal signs has two cross-copy sides; an inequality with a cross-copy side on the left reduces to an original triangle inequality. The remaining inequality follows from d(x,y)+d(x,z)+d(z,y)\le3\operatorname{diam}(d)<2R.
For a doubled point a, let c_a=(\widehat d(a,z))_z be its distance profile in \ell_\infty, and set Q=\conv\{c_a\}. The triangle inequality and coordinate a show \norm{c_a-c_b}_\infty=\widehat d(a,b). More generally, for q=\sum_b\theta_bc_b,
Indeed, convexity of the norm gives the upper bound, and coordinate a gives the lower bound. Thus the radius is the restriction of a linear coordinate function, independently of the representation of q. Set c_x=c_{x^+} and c_x^-=c_{x^-}. The identity \widehat d(x^+,b)+\widehat d(x^-,b)=R for every doubled point b proves Equation (2.7).
If \rho=\rho_x(q), the segment q_t=(1-t)q+tc_x has \norm{q_t-q}=t\rho and \rho_x(q_t)=(1-t)\rho. The segment q_t^-=(1-t)q+tc_x^- has \norm{q_t^--q}=t(R-\rho) and \rho_x(q_t^-)=\rho+t(R-\rho). These formulas prove the exact-motion assertion, including the endpoint cases. Convexity of Q keeps all segments in Q; the final assertion follows from Equation (2.8) and clamping.
For a pseudometric, first identify zero-distance points to apply Lemma 2.3. This identification concerns only the geometric point set. Every graph vertex, edge copy, hierarchy node, and center-vertex label is retained. In particular coincident vertex images do not contract the graph.
Figure 1: Spectral packing uses Euclidean points; balls and shells use the distance-profile realization with the same vertex labels. The radial paths are schematic: in the ambient norm, distance traveled along either indicated segment equals change of radius. The two segments need not form one straight segment in Q.
2.3 Transferring the bag and charging estimates
The next lemma extends the bag-selection and shell-charging arguments of [20, Propositions B.7, B.8, and B.10] to Q. We retain those constructions and their scalar accounting, but verify the geometric steps below: their stated cube hypotheses do not cover all tests in \mathcal N. The two charging alternatives explain the division into compact and assigned bags. Compact bags charge disjoint geometric objects. Assigned bags may overlap geometrically, provided their hierarchy labels separate the graph edges used for charging.
Use relative open balls B(c,\delta)=\{q\in Q:\norm{q-c}<\delta\} and strict shells B(c;a,b)=\{q\in Q:a<\norm{q-c}<b\}. An ordinary ball includes its center, whereas a shell with a=0 excludes it. Both are called radial objects. An ordinary ball B(c,b) has numerical inner radius a=0 and width b; a shell has width b-a. All radial tests and width formulas below apply to both types with these numerical radii, but membership and intersection always use the actual support. In particular, an unchanged ordinary ball keeps its center. A radial restriction to a\le a'<b'\le b means replacement by the strict shell B(c;a',b'), even when a'=0. Such a replacement is a subset of the old support; it is an operation, not an identification of a ball with a punctured shell. Proposed intervals of nonpositive width are discarded. A bag consists of mutually disjoint balls of a common radius \delta, centered at vertex images c_v. It is \beta-compact of type (\delta,\Delta) if it has at least two balls, its center diameter is at most \Delta, and \beta\Delta\le\delta|\mathrm{Bag}|. It is \eta-assigned to A if |\mathrm{Bag}|\ge\eta|O(A)| and every ball has a designated center vertex u\in A with an edge uv\in O(A) of length d(u,v)<\delta. A family has all its balls mutually disjoint and a common radius. A compact family has a common type (\delta,\Delta). An assigned family has one bag for each of a set of distinct assigned nodes. Bags assigned to the same node at one scale may always be merged: this preserves every witnessing edge, the assignment bound, and the total mass. Fix 0<\rho<1. A sequence of compact families is \rho-geometric when \Delta_{i+1}<\rho\delta_i; a sequence of assigned families is \rho-geometric when \delta_{i+1}<\rho\delta_i and its assigned nodes are distinct across families. In either case its mass is
Lemma 2.4 (Geometric transfer). Let p_v\in\R^{d_{\mathrm E}} be points for which d(u,v)=\norm{p_u-p_v}_2^2 is a pseudometric. Realize d in Q as in Lemma 2.3. Let U:\R^{d_{\mathrm E}}\to\R^{E(G)} be a contraction, change its row signs so a_e={\mathopen{\langle}u_e,p_u-p_v\mathclose{\rangle}}\ge0, and set
The following three assertions hold in Q.
- (i)
Let T be a nonempty set of nodes with N_A>0 and N_A\ge\alpha\sum_{e\in O(A)}d_e, where 0<\alpha\le1. Define
\begin{align*} J&=1+\lceil\log_2(256/\alpha^2)\rceil,& C_2&=128J^4,&\sigma&=\alpha/C_2,\\ L&=2+\lceil\log_2(1/\sigma)\rceil,& H_0&=1+\lceil\log_2(24/(\rho\sigma^2))\rceil,& C_1&=1024\epsilon^{-2}.\end{align*}If \beta>1, 0<\epsilon<1/3, 0<\rho<1, and \sigma^\epsilon\le(48\beta C_1)^{-1}, there is a \rho-geometric sequence consisting either of \beta-compact families or of \sigma^{1+2\epsilon}-assigned families, with
\mathsf M\ge \frac{\sigma^\epsilon}{384\beta C_1C_2LH_0} \sum_{A\in T}N_A. \tag{2.9} - (ii)
For G k-edge-connected, a \rho-geometric sequence of \beta-compact families with \rho\le1/12 and \beta\ge36 satisfies \mathcal E\ge(k/4)\mathsf M.
- (iii)
For a locally k-connected hierarchy, selected nodes satisfying |O(A)|\ge k\rho|P(A)|, and a \rho-geometric sequence of (24C_3/k)-assigned families, one has
\mathcal E\ge\frac{kC_4}{96C_3}\mathsf M \tag{2.10}provided C_4\ge3, \rho\le(6C_4)^{-1}, and C_3\ge2((C_4+1)+4(C_4+2)^2).
Proof. We follow the constructions in Sections B.2–B.4 of [20], keeping their scale choices and scalar potentials. All balls, shells, and intersections now lie in the continuous polytope Q. New shells inherit vertex centers, so Equation (2.8) remains available. We first obtain the bags, then explain how each of the two charging constructions operates in this realization.
Extraction and the spectral step. The two truncations and homogeneity arguments in [20, Section B.2.2] use only a_e^2\le d_e, nonnegative boundary sums, and multiplicity at most two. They select nonempty subsets O'(A)\subseteq O(A) retaining a fixed fraction of each squared boundary sum, and group the nodes so that both positive quantities a_e^2 and d_e vary by a factor less than four within F=\bigcup_AO'(A). For one such group put N=\sum_A|O(A)|, N'=|F|, c_1=\min_{e\in F}a_e^2, and c_2=\max_{e\in F}d_e. The truncation and grouping estimates give c_1N'\ge\sigma Nc_2. For the Euclidean points Y_v=Up_v and \widetilde\alpha=\sigma N/N' this implies
This is the exact hypothesis of the Euclidean spectral-packing Lemma B.3 of [20]; that lemma places no binary restriction on its points. Its selected centers have squared Euclidean separation at least 4r. Since
the corresponding Q-balls of radius r are disjoint. If b_0 is their number, the spectral lemma gives b_0r\ge\widetilde\alpha^\epsilon c_1N'/C_1. Shrink their common radius to \delta defined by b_0\delta=\widetilde\alpha^\epsilon c_1N'/C_1. Only the selected vertex labels pass from the Euclidean geometry to Q; a map on intermediate points is unnecessary.
The rest of the one-family construction uses a maximal disjoint collection of balls of radius D=\max\{\delta,2c_2\}, centered at images c_u for which u\in A and uv\in O'(A) for some A. Maximality puts every candidate center within 2D of a selected center: intersection of two relative balls implies this distance bound by the triangle inequality. Every endpoint center is within c_2 of an assigned endpoint, hence within 3D of a selected center. Grouping by those centers gives diameter at most 6D in the compact case. In the assigned case the witnessing edge has length at most c_2<D. The cardinality estimates of [20, Lemma B.6] give compactness, assignment strength, and radius range [\sigma c_1,12c_1/\sigma]. Its final grouping by dyadic size and then by residue class modulo H_0 is numerical: each scale lies between \sigma2^j and 24\,2^j/\sigma, so scales in the same residue class meet the stated geometric separation. The losses C_2, L, 2H_0, and 192\beta C_1/\sigma^\epsilon are exactly those in Equation (2.9). This proves (i).
Length charging and compact radial objects. The resource charged by both arguments is one fixed straight segment [c_u,c_v] of length d_e for each graph edge, retaining parallel edges as separate resources. For a radial object with numerical radii a<b, its clamped radial function is f(q)=\min\{b,\max\{a,\norm{q-c}\}\}. It is 1-Lipschitz and piecewise affine on each edge segment. If the object has vertex witnesses at radius at most a and at least b, all its intermediate radial cuts are nontrivial. Consequently
For disjoint radial objects, subdivide an edge segment at the finitely many breakpoints of these functions. At most one clamped function is nonconstant on each open subsegment, and its variation is bounded by that subsegment’s length. The total charge is therefore at most d_e, including edges along a boundary or of zero length. This proves the length bound of [20, Lemma B.9] in Q. For an ordinary ball, nonconstant portions of the clamped function lie at strictly positive radius. Its center contributes no charged length, but remains part of the ball in membership tests.
For compact bags, process the families in decreasing order of radius, as in [20, Proposition B.8]. An input ball inserted at the current scale is called fresh and is left intact until the next scale; all other live objects are called old. Thus a fresh ordinary ball becomes an old ordinary ball at the next scale unless a subsequent operation restricts it. Disjoint equal-radius balls have centers separated by at least 2\delta, since their midpoint belongs to Q. For any live object with center c and numerical radii a,b, call B(c_u,\delta) interior when
This conservative two-sided test also applies when the object is an ordinary ball, with a=0. If one ball of a compact bag is interior, its containing object is old, since fresh balls and unprocessed balls belong to the same disjoint family. All bag centers have radial values in an interval [l,u]\subseteq[a+\delta,b-\delta] of width at most \Delta. Replacing the old object by the strict shells with intervals (a,l-\delta) and (u+\delta,b) leaves room for all the new balls, including when the old object was ordinary. The extremal centers supply the new outer and inner witnesses; the previous witnesses supply the other two. Every inserted ball has its own center and a different bag center as witnesses. All supports are disjoint by 1-Lipschitzness of radius. When no interior bag remains, shrinking each old interval at both ends by 2\delta+\Delta separates it from every remaining ball. Indeed, failure at the lower margin puts the entire candidate at radius less than a+2\delta+\Delta, and failure at the upper margin puts it beyond b-2\delta-\Delta. This includes candidates near the center of an old ordinary ball: the shrink removes that center neighborhood. Witnesses are preserved because the inner radius increases and the outer radius decreases; an inner witness need not belong to the remaining strict shell. The capacities [w-6\Delta_i]_+ for all old objects and \delta_i-6\Delta_{i+1} for fresh balls depend only on widths and the inequalities 2\delta_i\le\Delta_i, 6\Delta_{i+1}\le\delta_i/2, and |\mathrm{Bag}|\delta_i\ge36\Delta_i, all verified here. The split loses numerical width (u-l)+2\delta, and the shrink loses 2(2\delta+\Delta), with the same positive-part accounting when a residual is discarded. Removing the center alone adds no width loss. A retained fresh ball has the same capacity after becoming old. Thus the split and scale-transition inequalities in the cited proof retain at least one quarter of the input mass as final radial-object width. Applying the preceding length bound proves (ii).
Assigned labels, pruning, and path charging. Assigned bags require the labeled records of [20, Section B.4.1]. We give their definitions because geometric overlap is allowed. Write \mathcal T[A] for the hierarchy subtree rooted at A, identifying its leaves with the vertices in A. A record H has an ordinary ball or shell as its support, an owner A_H, a set \mathcal P_H of strict descendants of A_H, and optionally one avoided strict descendant D_H. Define its conflict domain and leaf set by
omitting the final subtree when there is no avoided label. The record is called avoiding precisely when D_H is present. For center c and numerical radii a<b, validity means:
- (a)
the labels have the stated form, so A_H\in C(H);
- (b)
both endpoints of every edge of \delta_G(P), for every P\in\mathcal P_H, have radius at least b from c;
- (c)
some u\in L(H) has radius at most a and starts at least k/4 edge-disjoint paths to vertices of radius at least b. These paths lie in G[A_H], or in G[A_H\setminus D_H] for an avoiding record;
- (d)
geometrically intersecting records have disjoint conflict domains.
The initial paths in (c) need not avoid the predecessor subtrees in \mathcal P_H; condition (b) will remove those subtrees from the portions used for charging. Its inner witness is a graph vertex in L(H), not necessarily a point of the support: for a strict shell it can lie on or inside the excluded inner boundary.
For a node A assigned at scale \delta_i, its predecessors are the strict descendants assigned at earlier, larger scales. An input ball is noninsertable if it contains an endpoint of a boundary edge of any predecessor. Otherwise give it owner A, no avoided label, and excluded set equal to the predecessors.
At one scale, disjoint center-inclusive balls contain at most 2|P(A)| endpoint vertices of P(A). Thus a predecessor A, whose own scale is \delta_i, deletes mass at most 4\rho\delta_i|P(A)|, which the boundary ratio and assignment bound pay as in the source’s Lemma B.13. Deleting noninsertable balls and bags losing more than half their balls retains mass at least \mathsf M/2 and assignment at least 12C_3/k. Insertability puts the designated center vertex in its conflict domain: otherwise its witnessing edge in O(A) would be a forbidden predecessor-boundary edge whose endpoint lies in the ball. Another ball of the bag supplies an outer vertex; local connectivity supplies the required paths. The retained bag has more than one ball, since |O(A)|\ge k and its assignment is at least 12C_3/k. Thus the resulting input records satisfy (a)–(c), including when distinct vertices have coincident images.
For a valid collection, stop each witnessing graph path at its first outer vertex. It cannot enter an excluded predecessor subtree earlier, because the entering edge would have an endpoint inside the outer radius. On the resulting continuous path keep the portion from the last inner-radius point to the first outer-radius point. Its length is at least the record’s numerical width by 1-Lipschitzness. Apart from endpoints it lies in a<\norm{q-c}<b, which is contained in either type of support. For an ordinary ball a=0 and the center carries no charged length. Paths within one record are edge-disjoint. Both endpoints of every edge in a stopped path belong to L(H): an entrance into an excluded subtree, even at the stopping vertex, would have a preceding endpoint inside the outer radius, contradicting (b). Two records charging the same graph edge therefore have intersecting conflict domains, so (d) makes their actual supports disjoint and they charge disjoint open portions of that edge. This proves the source’s Lemma B.14 in Q, at rate k/4.
It remains to construct a valid arrangement with enough total width. Start with the empty arrangement and process scales in decreasing order and, within each scale, bags in increasing depth of their assigned nodes. As in the compact construction, original balls inserted during the current phase are fresh and remain intact until the next phase; all other records are old. A candidate J=B(c_u,\delta_i) is interior to a current record H with center c and numerical radii a,b when
A candidate interior to no current record is called a border candidate. In particular old ordinary balls participate in this test with a=0, including its lower margin. A record containing an interior candidate has width greater than 2C_3\delta_i, so it cannot be a fresh ball of width \delta_i. An interior candidate is contained in H. The processing order implies that the owner of any conflicting current record is an ancestor of the candidate’s owner A, and that A\in C(H). Two conflicting records therefore cannot both contain this candidate, by (d). The strict concentric restrictions defined above retain (a)–(c) with the old labels: the old inner witness still has radius at most the new inner radius, and the old paths still reach the smaller outer radius. This remains true when an ordinary ball is replaced by a shell and its center witness no longer lies in the support. Restricting both support and conflict domain preserves (d). Discard any proposed radial interval of nonpositive width. Such restrictions cannot turn a border candidate into an interior candidate. These are the order and inheritance properties of [20, Lemmas B.17–B.20].
Meeting a record and carving its interior. The following consequence of Lemma 2.3 identifies the record affected by a carving operation. If a live record H with center c and numerical radii r_1<r_2, and a vertex center z, satisfy
then B(z,\delta) meets the actual support of H. Choose a radius in (r_1,r_2) less than \delta away from \norm{z-c} and use the exact inward or outward motion to reach it. Its traveled distance is less than \delta. There is no radius-range obstruction: condition (c) provides an outer vertex witness, so r_2\le\operatorname{diam}(d)<R. For an ordinary ball r_1=0; the chosen radius is positive and belongs to that ball, even when z=c and outward motion is needed. This replaces motion toward the binary center or its opposite cube vertex in [20, Section B.4.3].
At scale \delta, process the interior candidates of a bag assigned to A while at least half its original balls remain interior and untreated. Candidates that cease to be interior are kept as border candidates. Carving an avoiding shell around an interior candidate replaces its radial interval (r_1,r_2) by (r_1,q-\delta) and (q+\delta,r_2), and inserts the candidate. Here q is its center’s radius from the shell center. Every avoiding record is indeed a strict shell: input records are nonavoiding, only the central shell H_4 below introduces an avoided label, and later restrictions are strict shells. Radial Lipschitzness gives disjointness; witnesses and labels survive in the restrictions. If no remaining interior candidate belongs to an avoiding shell, the other two operations first split G[A^*\setminus A] into j\le2|O(A)|/k induced subgraphs that are k/4-edge-connected. This count follows by successive cuts smaller than k/4 and the k-connectivity of G[A^*]; it is independent of the embedding. Assignment and the half-bag loop condition give one piece adjacent along edges of length less than \delta to at least 3C_3 candidate centers. Radial coordinates of these neighbors differ by less than \delta from those of their candidate centers.
Choose a nonavoiding record H containing one of those candidates in its interior, with center c and numerical radii r_1,r_2, and write \varrho(v)=\norm{c_v-c}. It may be an old ordinary ball, in which case r_1=0. Let [a,b]\subseteq[r_1,r_2] be the radial range of the neighbors in the selected piece, clipped to this numerical interval. Select for treatment the m still-interior candidates whose centers have radii in (a-\delta,b+\delta). Each meets the chosen record by the preceding exact-motion argument. All candidates of the bag have the same labels, so each has conflict domain meeting C(H). If such a candidate is interior to another record H', its entire ball lies in H', so H and H' intersect. The processing-order property puts its owner A in both conflict domains, contrary to (d). Thus every selected candidate is interior to H itself. The radial count in the cited proof gives m\ge3(C_3-1) in the dense case below and b-a\ge(C_3-1)\delta in the sparse case. It uses only the 3C_3 adjacent centers, their interior margins, and the fact that neighbor radii differ by less than \delta.
For the dense case, with m\delta>3(b-a), retain intervals (r_1,a-2\delta) and (b+2\delta,r_2) and insert the m balls. The expanded radial interval and Lipschitzness give every required separation. For the sparse case m\delta\le3(b-a), retain (r_1,a) and (b,r_2) and create the central shells H_3=B(c;a+\delta,b-\delta) and H_4=B(c;a,b). Give H_3 owner A, no avoided label, and the old excluded nodes strictly below A. Give H_4 the old owner and excluded set, and avoided label A. Their domains are respectively C(H)\cap\mathcal T[A] and C(H)\setminus\mathcal T[A]. The old owner is a strict ancestor of A. An original ball with owner A cannot come from an earlier scale, since assigned nodes are distinct across families; at the current scale it is disjoint from every unprocessed candidate. A synthetic shell with owner A can only have been created while processing this same bag. It has already treated every then-interior candidate in its expanded interval; later restrictions only reduce its support, and border candidates never become interior. Hence neither an original ball nor a synthetic shell with owner A can be the chosen record. Thus both new labels have the required form. For the changed-label path witnesses, extremal neighbors v_1,v_2 in the selected piece and their adjacent candidates u_1,u_2\in A satisfy
Connectivity of G[A] supplies k paths for the inner central shell; connectivity of the selected piece supplies at least k/4 paths for the avoiding shell. Their initial vertices avoid excluded subtrees: membership in one would make the short edge u_1v_1 an excluded boundary edge with an endpoint inside the old outer radius, or make that excluded subtree an ancestor of A, contradicting A’s conflict membership. The sparse-case width bound gives a+\delta<b\le r_2, so the initial vertices used here lie strictly inside the old outer radius. This verifies (c) for both new labels; (b) follows from the smaller outer radii and excluded sets. Other records inherit separation by support and conflict-domain inclusion. Remaining interior candidates have centers outside (a-\delta,b+\delta), so miss both central shells. If a=0, H_4 excludes its center but may still use v_1 at radius zero as its inner witness, as condition (c) permits.
The scalar accounting and the phase transition. The potentials in Section B.4.3 are \delta_i-C_4\delta_{i+1} for fresh balls, [w-C_4\delta_i]_+ for other nonavoiding records, and the latter divided by 2(C_4+2) for avoiding records. An original ball becomes old when its phase ends and then uses the second formula with width equal to its radius; if retained unchanged, it still has its center-inclusive support. These functions use the same numerical widths and radii in Q. The three replacements have formal width losses 2\delta across the two avoiding residual shells in the first operation, (b-a)+4\delta across the two nonavoiding residual shells in the second, and 2\delta across the three nonavoiding pieces in the third. Its numerical inequalities preserve old credit and supply C_4\delta/(6C_3) per treated candidate, counting sparse-case candidates as treated even though their balls are not inserted. Finally, Section B.4.4 either retains every record when the gain from changing scale supplies the required border credit, or shrinks every old object, including old ordinary balls, at both ends by (C_3+1)\delta_i and inserts remaining border balls when the gain is insufficient. For a conflicting old object, border status means the candidate center has radius at most a+C_3\delta_i or at least b-C_3\delta_i. Its whole ball therefore lies below the new inner radius or above the new outer radius, respectively. This proves separation also at the center of an old ordinary ball; fresh balls are disjoint within the current family. Restrictions retain witnesses. Each old width decreases by 2(C_3+1)\delta_i, unless the object is discarded, while the potential threshold decreases from C_4\delta_i to C_4\delta_{i+1}. These are the same changes for a ball and a shell. The source’s width calculation bounds the lost potential by half the inserted mass, leaving at least C_4/(6C_3) of each border ball’s radius for its node. The half-bag stopping rule leaves final width at least C_4/(12C_3) times the retained mass. Combined with the pruning factor 1/2 and the path-charging rate k/4, this is exactly Equation (2.10).
Thus the inherited constructions give (i)–(iii), with the same scalar losses and with every length charge measured by \mathcal E=\sum_e d_e in the profile realization.
2.4 Choosing parameters and responding to a partition chain
Proof of Theorem 2.1. If \mathcal M is empty, a sufficiently small positive centered identity satisfies Equation (2.2). Otherwise use Lemma 2.2. Fix one of its embeddings and row-orthonormal systems, with \mathcal E>0, and set
Let T consist of the marked nodes with positive N_A and N_A\ge\alpha\sum_{e\in O(A)}d_e. Boundary multiplicity at most two gives
If T is nonempty, apply Lemma 2.4(i). Its parameters obey
The smallness condition holds for all sufficiently large absolute h. So does the assignment requirement, because
The marked-node condition implies |O(A)|\ge|P(A)|/h\ge h\rho|P(A)|. For large h, \rho\le1/18; also 10^4\ge2(4+4\cdot25)=208. Both charging conclusions of Lemma 2.4 therefore apply, according to the family type, and give the common bound
Together with Equation (2.9), this yields
Indeed \sigma^\epsilon=h^{-2/25}C_2^{-1/10}, so the exact logarithmic exponent before rounding upward is 32/5<7. Including Equation (2.12), or using it alone when T is empty, every ratio in Equation (2.4) is at most
The exponent margins are 1/40 and 29/200, respectively. Increase h_0 so the bound is at most h^{-31/40}/2. Then p_*\le h^{-31/40}/2, and the defining property of the infimum supplies a feasible positive definite D with marked averages less than h^{-31/40}. No attainment assumption is used.
For a fixed connected ambient graph H, define
This set is nonempty, convex, and compact. It contains L_H; closedness is immediate, and the test \Id_{\mathsf E} bounds \tr X by 3\tr L_H. For X\succ0 write R_X(e)=b_e^TX^{-1}b_e. Two elementary identities used below are
The first follows by inverse order, and the second by congruence with X^{-1/2} and the single nonzero eigenvalue of a rank-one matrix.
Proposition 2.5 (Simultaneous response). Let H be connected and let G\subseteq H be a spanning subgraph. Let r be a sufficiently large integer, put h=\lfloor r/2\rfloor, and suppose G and the subgraphs induced by all parts of a nested sequence of partitions are h-edge-connected, with the singleton condition vacuous. If 0<s\le r^{1/4}, there is Y\in\mathcal K_H such that, at every partition \mathcal P in the sequence, all but at most r^{-1/3}|E_G(\mathcal P)| crossing edges satisfy
Here E_G(\mathcal P) denotes the edges whose endpoints lie in different parts of \mathcal P.
Proof. Use the dyadic assembly of [20, Lemma 4.2], with the hierarchy estimate and threshold just proved; we give the counting argument to specify both constants. In each occupied bin 2^a\le |E_G(\mathcal P)|<2^{a+1} choose the finest partition. List these representatives from fine to coarse as \mathcal P_0,\ldots,\mathcal P_{\ell-1}, and append \mathcal P_\ell=\{V\}. Put B_i=E_G(\mathcal P_i) and M_i=|B_i|, with M_\ell=0. Distinct parts of these representative partitions, together with V and singleton leaves, form a locally h-connected hierarchy. Mark precisely the nodes with |O(A)|\ge|P(A)|/h, and take D from Theorem 2.1. Then
because Y\succeq L_H and, for every Z\in\mathcal N, {\mathopen{\langle}Y,Z\mathclose{\rangle}}\le{\mathopen{\langle}L_H+L_G,Z\mathclose{\rangle}}\le2{\mathopen{\langle}L_H,Z\mathclose{\rangle}}.
At transition j to j+1, the parent of each changing part is the part of \mathcal P_{j+1} containing it. Every disappearing edge in B_j\setminus B_{j+1} belongs to parent boundaries of changing parts, whose total full-boundary size is at most 2M_j. Unmarked parts therefore cover at most 2M_j/h such edges. For marked parts, Equation (2.15) and Markov’s inequality give
Thus at most 2(h^{-1}+6s h^{-31/40})M_j disappearing edges fail Equation (2.16). Double counting only increases this upper bound.
There is at most one representative per dyadic bin, and its bin index strictly decreases. Hence \sum_{j=i}^{\ell-1}M_j<4M_i. Each edge of B_i disappears at exactly one subsequent transition, so its bad-edge count is at most 8(h^{-1}+6s h^{-31/40})M_i. For a skipped partition with positive crossing count M, its representative is finer and has M_i<2M. Consequently its bad-edge count is at most
for a sufficiently large absolute cutoff. The final inequality uses 21/40-1/3=23/120>0. Partitions with no crossing edges need no estimate. One matrix Y therefore works for the whole nested sequence.
3 Constructive shortcut extraction
We now turn the simultaneous response of Proposition 2.5 into an algorithm. Throughout this section, an explicit multigraph has distinct labels for its parallel edges, and loops are discarded. Write E_H(\mathcal P) for the edges crossing a partition \mathcal P of the vertex set. Matrices act on \one^\perp, with its inherited Euclidean inner product. We retain the cone \mathcal N and compact convex set \mathcal K_H from the preceding section:
Here A\mathbin\bullet Z=\tr(AZ) always means the inherited trace, even when rational, nonorthonormal coordinates are used for computation.
The construction follows the packing-preserving sparsification strategy of [20]. Convex continuation produces a rational shortcut together with a large integer packing supported on its low-resistance edges. Nonnegative capacities permit partition uncrossing; the nearly tight partitions then have highly connected parts, which is precisely the input required by the simultaneous geometric response.
3.1 A ramp of packing capacities
We use two standard algorithmic inputs in precise forms. The Nash–Williams–Tutte tree-packing theorem [19, 26] says that a multigraph contains q edge-disjoint spanning trees if and only if
see [14, Theorem 1]. A maximum union of q graphic matroids can be constructed by matroid partition, originating with Edmonds [8]; we use the polynomial-time independence-oracle algorithm of [24, Theorem 14]. The algorithm returns disjoint forests of maximum total cardinality. Their total size is q(n-1) exactly when all q forests are spanning trees. Acyclicity is a polynomial-time independence test, including for parallel edges. We reject q(n-1)>m before invoking this procedure; thus the number of matroid copies is polynomial for an explicit graph.
Proposition 3.1 (Constructive shortcut extraction). There are absolute constants A and r_0 such that the following holds. If an explicit multigraph H on at least two vertices contains r\ge r_0 edge-disjoint spanning trees, one can deterministically compute a rational X\in\mathcal K_H and at least
edge-disjoint spanning trees, every edge e of which satisfies b_e^TX^{-1}b_e\le r^{-1/4}. The running time and output encoding length are polynomial in |V(H)|+|E(H)|.
Fix such an H, put m=|E(H)|, and set
where g is dyadic. Comparing eighth powers computes g exactly with O(\log r) bits. At a parameter s>0 and matrix X\in\mathcal K_H, define
The maintained invariant is
Initially take s=1/2, X=L_H, and Q=r. Since L_H\succeq b_eb_e^T, each R_e(L_H)\le1, so u_e=1 and the initial invariant follows from the given packing.
One step replaces
where Y\in\mathcal K_H is to be found. Steps are performed while s^4<r, an exact rational comparison. The final step may overshoot r^{1/4}; every response is invoked at an old parameter s\le r^{1/4}. There are O(t^{-1}(1+\log r)) steps, since \log(1+t)\ge t/2. Consequently
after increasing the absolute cutoff r_0.
Let G be the active subgraph with edges u_e>0. Choose variables 0\le y_e\le1 for e\in E(G) and impose
For these variables define concave lower capacities on all edges of H:
They are nonnegative, in fact a_e\ge\kappa-4t=7\kappa/8. This small baseline will also make the uncrossing argument valid.
To check the lower bound, recall that X\succeq\alpha b b^T is equivalent to \alpha\le(b^TX^{-1}b)^{-1} for X\succ0. Thus X\succeq sp_e b_eb_e^T, and Equation (3.8) gives
Indeed the numerator of the difference in the last inequality, divided by t, is (1-5t)y_e+4+4t-2p_e\ge0, since p_e\le2 and t<1/5. Taking the ramp at s^+,X^+, including both its upper cap and its lower truncation, proves
Off G this follows just from u_e^+\ge0.
Lemma 3.2 (A feasible continuation response). Under Equations (3.5) and (3.7), with s\le r^{1/4}, there exist Y\in\mathcal K_H and y satisfying Equation (3.8) and
Proof. Let \mathcal C be the compact convex set of admissible (Y,y) before the partition inequalities are imposed. It is nonempty: take Y=L_H and y=0. Put q=Q-grt>0 and let
Each slack is continuous and concave. Its vector image need not be convex, but the downward set
is convex and closed. Convexity follows coordinatewise from concavity; closedness follows by taking a convergent subsequence of witnesses in \mathcal C. The set \mathcal D is unbounded downward. If it does not meet the nonnegative orthant, its distance from that orthant is positive: the norm of the negative part of S(y) has a positive minimum on the compact set \mathcal C, and passing downward cannot reduce that norm. Separation therefore supplies nonnegative weights w_{\mathcal P}, normalized to sum to one, for which
There are finitely many partitions. Hence F is continuous on their probability simplex and has a minimizer. Among minimizers choose one maximizing \sum_{\mathcal P}w_{\mathcal P}|\mathcal P|^2. Its support is a chain under refinement. To prove this, suppose incomparable \mathcal P,\mathcal Q have positive mass. Move equal mass from them to their common refinement \mathcal P\wedge\mathcal Q and finest common coarsening \mathcal P\vee\mathcal Q. For each edge,
Moreover,
For the second inequality, form the bipartite graph whose vertices are parts of \mathcal P and \mathcal Q and whose edges are their nonempty intersections. Its edges count refinement parts, and its connected components count coarsening parts; edges plus components are at least vertices. Since a_e\ge0 and q>0, uncrossing decreases the weighted slack for every (Y,y), hence cannot increase F. Writing a=|\mathcal P|, b=|\mathcal Q|, c=|\mathcal P\wedge\mathcal Q| and d=|\mathcal P\vee\mathcal Q|, incomparability gives c>\max(a,b) and d<\min(a,b). Thus
This contradicts the tie-breaking choice. The one-part partition has zero slack and is comparable with every partition, so it creates no exception.
It remains to satisfy Equation (3.11) simultaneously on any chain. Let the old slack in Equation (3.5) be \sigma_{\mathcal P}\ge0. If \sigma_{\mathcal P}>1, the worst possible loss 4tm<1 already leaves the desired inequality. Retain only partitions with \sigma_{\mathcal P}\le1, omitting the one-part partition. Every part of every retained partition induces an h-edge-connected graph in G, where h=\lfloor r/2\rfloor. Indeed, split one such part by any nontrivial internal cut. Subtracting the old partition capacity from the invariant for the refined partition shows that the internal cut has capacity at least Q-1. Removing all baselines loses less than \kappa m<1, and u_e\le1 then shows that the active internal cut has more than Q-2\ge h edges. The same argument using a two-part partition at the root gives more than Q-1 active edges across every root cut. Singleton parts require no check.
Apply Proposition 2.5 to this chain, with its root, and set y_e=1 on edges satisfying Y\succeq6s b_eb_e^T, and y_e=0 otherwise. These choices satisfy Equation (3.8). Fix a retained partition, write d=|\mathcal P|\ge2 and M=|E_G(\mathcal P)|, and call its at most r^{-1/3}M exceptional crossing edges bad. Good edges never lose capacity; bad edges lose at most 4t each. If M\le8r(d-1), the total loss is at most
for sufficiently large r, as required.
If M>8r(d-1), near-tightness gives \sum_{E_G(\mathcal P)}u_e\le Q(d-1)+1\le r(d-1)+1. Fewer than half of these M edges can have u_e>1/2: their number is at most 2r(d-1)+2<M/2 for the chosen cutoff. Each good edge with u_e\le1/2 gains exactly t, since t<1/2. The total gain minus loss is therefore at least
This also proves the desired inequality. Every chain thus admits a simultaneous nonnegative slack vector, contradicting Equation (3.12). The lemma follows.
3.2 Exact separation and a uniform interior ball
The existence lemma leaves a margin grt beyond the actual target Q^+=Q-2grt. We next use that margin to compute a response, including when the stronger solution has y_e=0 or 1.
For distinct vertices put T_{ijk}=b_{ij}b_{ij}^T+b_{jk}b_{jk}^T-b_{ik}b_{ik}^T. The dual cone has the exact representation
Here and below all ordered distinct triples may be used; repetitions of an identical generator are harmless. To verify closedness, note that \tr T_{ijk}=2. If matrices on the right converge, their traces bound both \tr P and \sum\lambda_{ijk}. The PSD summands and coefficients therefore have convergent subsequences. The represented cone is closed, and its dual is exactly the PSD cone intersected with all triangle halfspaces, namely \mathcal N. The finite-dimensional bipolar theorem proves Equation (3.13). This trace argument uses full centered matrices; an ordinary trace in arbitrary reduced coordinates would not justify it. Also, for any connected G, choosing 0<\epsilon<\lambda_{\min}(L_G|_{\one^\perp}) makes L_G-\epsilon I positive definite and hence interior to \mathcal N^*. This supplies strict conic feasibility whenever it is needed in the shortcut domain.
Use variables Y, \lambda_{ijk}\ge0, and y_e,z_e for e\in E(G). Besides Equation (3.8), impose
Define z_e=\kappa off G and add
By Equation (3.13), the two LMIs in Equation (3.14) describe exactly Y\in\mathcal K_H. The two upper bounds on z_e describe z_e\le a_e(y).
Lemma 3.3 (Partition separation by minimum spanning trees). For nonnegative rational capacities z and rational q\ge0, the inequalities z(E_H(\mathcal P))\ge q(|\mathcal P|-1) have an exact polynomial-time separation oracle. Consequently the full feasible set defined by Equations (3.8), (3.14), (3.15) and (3.16) has such an oracle at rational points.
Proof. The partition inequalities are equivalent to
where \operatorname{MST}(\ell) is minimum spanning tree length in H. For one direction, assign length one to edges crossing a partition and zero to all other edges. Every spanning tree has at least |\mathcal P|-1 crossing edges. Conversely, let \mathcal P_a be the components of the subgraph of edges of length less than a. Kruskal’s algorithm gives
Every edge crossing \mathcal P_a has length at least a, so integration of the partition inequalities gives q\operatorname{MST}(\ell)\le\sum_e z_e\ell_e.
To separate Equation (3.17), solve the rational linear program
All facet coefficients have polynomial encoding length. A minimum spanning tree supplies exact separation for the exponentially many tree constraints. The rational polyhedral optimization theorem [12, Theorem 6.4.9] therefore computes the exact optimum and a rational optimizer in polynomial work. The optimum is nonnegative. If it is zero all inequalities hold; if positive, the returned length vector gives a violated valid linear inequality in z.
The scalar constraints have immediate rational separators. Exact symmetric elimination either certifies a rational symmetric matrix as PSD or produces a rational vector of negative quadratic form. Applied to an affine matrix constraint, that vector supplies a rational linear separator of polynomial encoding length. This completes the oracle.
Lemma 3.4 (Quantitative feasibility and bounded output denominators). Every continuation step can be computed in polynomial binary time. Its returned variables may be taken on a fixed rational grid whose encoding length depends only on n+m, not on the denominators of the old capacities u_e.
Proof. We give deliberately loose uniform bounds. Put P=n+m+2\ge5 and use the upper-triangular entries of the upper-left (n-1)\times(n-1) block as free coordinates of a centered symmetric matrix. If that block is A, its full completion is CAC^T, where C=[e_1-e_n\ \cdots\ e_{n-1}-e_n]. Thus a free-coordinate perturbation of Euclidean norm \eta changes the full matrix in operator norm by at most 2P\eta. Include \lambda,y,z as ordinary scalar coordinates. Their total number D is at most P^3.
A connected unweighted multigraph has
For the first bound, for a centered unit vector choose its largest and smallest coordinates and a path between them of length at most n-1. The coordinate range is at least n^{-1/2}, so Cauchy–Schwarz along that path already gives energy at least 1/(n(n-1))\ge P^{-3}.
Consider an auxiliary point, without requiring its partition constraints:
There are at most P^3 generators, each of norm at most 6, so their weighted sum has norm at most 6P^{-5}<\mu/2. Since s\le r^{1/4}\le m+1<P and \|b_eb_e^T\|=2, the response LMI at this point has margin at least 2\mu-12P^{-7}>\mu. The other two LMIs have margins at least \mu/2. The \lambda and lower y faces have margin P^{-8}, the upper y face has margin at least 1/2, and the z lower and upper faces have margins at least \kappa/2 and 1, respectively. Finally
All scalar normal norms and affine matrix Lipschitz constants are at most 20P^3 in these coordinates. It follows that the entire ball of radius
about this auxiliary point satisfies all non-packing constraints. In particular these estimates are uniform even when an active u_e is extremely small.
By Lemma 3.2, choose a stronger feasible point x_*, using z_e=a_e(y) and any representation Equation (3.14). Let \beta=grt. Every nontrivial partition has slack at least \beta(|\mathcal P|-1)\ge\beta at x_* relative to Equation (3.16). Moreover,
At the auxiliary point every such slack is at least -P^2, because all capacities are nonnegative and Q^+\le r\le m. Mix a fraction \theta=P^{-8} of the auxiliary point into x_*. Since P\ge5, the new partition slacks are at least (1-\theta)\beta-\theta P^2\ge\beta/2. Convexity gives a ball of radius \theta\rho_0=P^{-28} satisfying the non-packing constraints about the mixture. A partition normal has at most m unit coefficients in the z coordinates, so its norm is at most \sqrt m. Thus the smaller ball of radius
satisfies every partition constraint as well. Their exponential number does not change this uniform estimate.
There is also a uniform outer ball. Testing Equation (3.1) against the centered identity gives \tr Y\le6m. Taking traces in the second LMI of Equation (3.14) gives \sum\lambda_{ijk}\le3m. Together with 0\le y_e\le1 and 0\le z_e\le\kappa+1\le2, these bounds place all free coordinates in the ball of radius P^3. We may impose the larger radius 2P^3 with slack. This ball also has an exact rational separator: for a rational query a with \|a\|>R, the inequality a\cdot x\le(R^2+\|a\|^2)/2 contains the radius-R ball and strictly excludes a, by Cauchy–Schwarz and the arithmetic–geometric mean inequality. All ball constants have logarithmic encoding length in P. The rational central-cut ellipsoid procedure, using Lemma 3.3, now finds an exactly feasible point in polynomial work [12, Theorem 3.2.1 and its proof]. Indeed, use our exact membership test at every oracle query and choose the enclosing-volume cutoff below (2\rho/D)^D, the volume of a coordinate cube contained in the proved radius-\rho inner ball. The small-volume outcome is impossible, so the algorithm must terminate at an exactly accepted rational point. This argument uses the displayed positive inradius; it does not assume exact solvability of an arbitrary semidefinite feasibility problem.
To bound the returned denominators independently of those in u, put L=\lceil\log_2P\rceil, \eta=2^{-32L} and \gamma=2^{-36L}, and instead find x such that
where \mathcal F is the full step feasible set, including the outer bound. The intersection of these 2D translates still contains a ball of radius at least \rho-\eta\ge3\rho/4, and has a separation oracle by translating the queries. Use the corresponding volume cutoff with 3\rho/4 in place of \rho. Convexity implies that the cross-polytope \{x+v:\|v\|_1\le\eta\} lies in \mathcal F. Round each coordinate of x to the fixed dyadic mesh \gamma. Its total rounding error is at most D\gamma/2\le\eta/(2P)<\eta, so the rounded point remains feasible. The outer bound gives at most 39L+O(1) bits per coordinate. This argument does not round a boundary solution without a margin.
Finally s and Q have polynomial encoding length throughout the prescribed schedule. At a rational X\succeq L_H, its centered inverse and all old u_e are computed exactly with polynomial bit operations. Every new Y lies on the fixed grid just described. Forming X^+=(1-t)X+tY increases encoding length by only a polynomial additive amount per step. Over the polynomial number of steps neither denominators nor oracle work can cascade beyond polynomial size.
Proof of Proposition 3.1. Apply Lemmas 3.2 and 3.4 at every step. The computed capacities satisfy Equation (3.16); Equation (3.10) therefore preserves Equation (3.5) with target Q^+. At termination s\ge r^{1/4}, and every active edge has R_e(X)<1/s\le r^{-1/4}. Dropping the baselines loses less than one across any partition, and u_e\le1 gives
Hence Equation (3.2) supplies \lfloor Q-1\rfloor disjoint spanning trees. Construct them by the graphic-matroid union procedure stated above. By Equation (3.7), their number is r(1-O(r^{-1/8}(1+\log r)))-O(1), which is at least (1-Ar^{-1/16})r after enlarging A and r_0. All steps have the claimed polynomial bit complexity.
4 A rank-preserving normalized frame
The shortcut controls effective resistances. A second vector system encodes the spanning-tree packing, so that signing can preserve both properties simultaneously. The normalization uses the log-determinant variational method for radial isotropic position [7, Section 2.2]. We prove the approximate positive-weight form and its bit bounds directly, so no attainment assumption is needed.
Lemma 4.1 (A computable normalized frame). Suppose B is the union of q edge-disjoint spanning trees, where r/2\le q\le r and r exceeds an absolute constant. There are vectors z_e\in\R^{n-1}, obtained from faithful reduced incidence columns by one common invertible linear map and positive individual scalings, such that
They admit rational approximations to Euclidean error 2^{-b} in time polynomial in n+|B|+r+b. An exact specification uses polynomial-bit positive rational edge weights followed by whitening; in particular, every subset has exactly its original incidence rank.
Proof. Delete one row of the incidence matrix and write the resulting columns as c_e. Put M=|B|=q(n-1) and consider
By Cauchy–Binet, \det N(d)=\sum_T\exp(\sum_{e\in T}d_e), where T ranges over the spanning trees of B: reduced incidence determinants of trees have absolute value one, and other maximal minors vanish. Keeping the q specified disjoint trees and applying the arithmetic–geometric mean inequality gives
Also f(0)\le(n-1)\log(2M), so the initial gap above the infimum is bounded by n\log(2M). Differentiation gives
The Hessian is the covariance matrix of the tree indicator under the probability distribution proportional to \exp(\sum_{e\in T}d_e). Hence it is PSD with operator norm at most M, since these indicators have squared norm n-1\le M. Each leverage score in Equation (4.3) lies in [0,1]; consequently \|\nabla f\|\le\sqrt M.
Start at d=0. At each step compute a rational gradient estimate v with \|v-\nabla f(d)\|\le1/(10r^2). If \|v\|\le2/r^2, stop; otherwise update d\leftarrow d-v/(2(M+1)). The norm comparison can be made by squaring rational quantities. The Hessian bound yields
At a nonstopping step the gradient error is at most \|v\|/20. Thus the decrease is at least \alpha\|v\|^2/2\ge2\alpha/r^4. The gap bound permits at most O((M+1)r^4 n\log(2M)) such steps. At termination
Here is an explicit precision justification for this descent. Its iteration bound is prescribed in advance, and each coordinate changes by at most two in one step. Thus |d_e|\le B_0 for a known polynomial B_0 in n+M+r. On that entire box,
The matrix N(0) is positive definite, has norm at most 2M, and has positive integral determinant. Its smallest eigenvalue is therefore at least (2M)^{-(n-2)}. The upper norm and inverse-norm bounds for N(d) have polynomial logarithms. Computing exponentials to polynomially many bits, forming rational approximations to N(d), and solving rational linear systems therefore evaluates Equation (4.3) to the requested error in polynomial bit work. For example, the identity \widetilde N^{-1}-N^{-1}=\widetilde N^{-1}(N-\widetilde N)N^{-1} controls the inverse error once \|\widetilde N-N\|\le\lambda_{\min}(N)/2. Gradient estimates may be rounded on one fixed dyadic grid 2^{-b_0} sufficiently fine for the stated error. Starting at zero, every iterate then lies on the grid [2(M+1)2^{b_0}]^{-1}\mathbb Z^M. The prescribed iteration and magnitude bounds therefore keep every d_e a polynomial-bit rational.
At the terminal d, choose positive rational weights a_e satisfying |a_e/\exp(d_e)-1|\le1/(100r^2) and put N_a=\sum_e a_ec_ec_e^T. Compute its rational diagonal elimination N_a=L D_aL^T with positive diagonal D_a, set F=D_a^{-1/2}L^{-1}, and define z_e=\sqrt{a_e}Fc_e. Then FN_aF^T=I. The relative matrix bounds on N_a and Equation (4.4) imply
Their outer products sum exactly to I. All a_e are strictly positive and F is invertible, proving rank preservation.
For the promised approximations, perform exact rational diagonal elimination on the positive definite N_a and then approximate the positive square roots of its pivots. Every pivot and inverse pivot has polynomial logarithmic bounds, either by the preceding spectral bounds or by determinant bounds for rational principal submatrices. Triangular solves and scalar square roots therefore approximate F and all z_e to 2^{-b} with polynomially many guard bits and polynomial work. These approximations refer to the single exact frame just defined; rounding does not redefine its subset ranks.
5 Exact rational padding and certified signing
The deterministic signing theorem proved in Appendix A has an exact input promise. For explicit rational columns v_1,\ldots,v_M\in(\Q+i\Q)^d satisfying \sum_i v_iv_i^*=I, it returns signs \sigma_i\in\{-1,1\} with
in time polynomial in the full binary input length. This is Theorem A.1, a quantitative form of the method of Ezeunala and Jiang [9]. Real rational columns are a special case. We first establish an elementary exact factorization, then prove the transfer required here, including identity completion and a rational success certificate.
Lemma 5.1 (Rational positive semidefinite decomposition). Every rational Hermitian positive semidefinite matrix A can be written exactly as
in polynomial bit time, with M and the total encoding length of the columns polynomial in the encoding length of A. If A is real, the columns may be taken real. For A=0, the sum may be empty.
Proof. If a positive semidefinite matrix has all diagonal entries zero, it is zero, since its two-by-two principal minors give |a_{ij}|^2\le a_{ii}a_{jj}. Otherwise permute a positive diagonal entry into the first position and write
Here d is positive rational and the Schur complement is positive semidefinite: evaluate the quadratic form of A at (-b^*x/d,x). Repetition gives a rational pivoted LDL^* factorization, or equivalently A=\sum_j d_j u_ju_j^* with positive rational d_j and rational complex u_j.
All elimination entries have polynomial encoding length. To see this directly, clear the input denominators by one positive integer q. The resulting Gaussian-integer matrix has polynomial-bit entries, and every minor has polynomial bit length by the determinant expansion. At any pivot order, the pivots and elimination coefficients are ratios of these minors, with an additional factor q for the pivots. There are at most n pivots, so rational elimination takes polynomial bit time.
For a pivot d=a/b>0 with positive integers a,b, expand ab=\sum_k c_k4^k, where c_k\in\{0,1,2,3\}. Then
Replace d u u^* by c_k copies of the outer product of (2^k/b)u for each k. The number of copies and their bit lengths are polynomial in those of a,b,u. This proves every assertion, including the real case.
Lemma 5.2 (Checked signing of the stacked frame). Let X and the union B of q trees be as in Proposition 3.1, retaining r/2\le q\le r trees, and let z_e be the frame of Lemma 4.1. Put
For an absolute constant C_s, a deterministic polynomial-time procedure finds A\subseteq B satisfying
An exact polynomial-time rational PSD test certifies the output.
Proof. The first block of Equation (5.2) is expressed in orthonormal coordinates on \one^\perp; its particular orthogonal basis is irrelevant. Since L_B\preceq L_H\preceq X, its outer-product sum is at most I, while the second block sums to I. Block Cauchy–Schwarz therefore gives
Individual squared norms are at most r^{-1/4}+(1+4/r)/q\le5r^{-1/4} for the chosen cutoff.
Write n=|V(H)|, m=|E(H)|, and P=n+m+2, as in Lemma 3.4. The centered positive definite X has polynomial-bit rational entries, with smallest eigenvalue at least P^{-3} and norm at most 6m. As in the proof of Lemma 4.1, elimination, square-root approximation, and solves compute a whitening of this block to any requested polynomial number of bits. More explicitly, in the rational coordinates used above write X=CA_XC^T and b_e=Cc_e. Then c_e^TA_X^{-1}c_f=b_e^TX^{-1}b_f, so whitening A_X gives the same Gram matrix as the displayed block and differs from it only by an orthogonal map. The smallest eigenvalue of A_X is at least P^{-3}/n, because the centered projection of (v,0) has squared norm at least \|v\|^2/n. Thus this computation has the same polynomial precision bounds. Combining it with Lemma 4.1, compute rational columns a_e approximating w_e/2 to Euclidean error at most 1/(1000|B|r). Because Equation (5.4) implies \|w_e/2\|\le1, the outer-product identity
shows that
The same estimate controls every signed sum, without knowing the signs. Also \|a_e\|^2\le3r^{-1/4}.
Apply Lemma 5.1 to the rational PSD residual I-\Sigma, obtaining polynomially many polynomial-bit real rational columns v_1,\ldots,v_J with
In particular \|V\|_{\op}\le1 and each \|v_j\|\le1. Extend the data columns by zeros in J additional coordinates. Set N=2r. For each j, add N^2 columns
where f_j is the jth extra coordinate vector and exactly half the \tau_{j,k} equal 1, half -1. The parity requirement holds because N is even. Their unsigned sum is
Together with the extended data this is exactly the identity. Every padding squared norm is at most 2/N^2, so the maximum squared norm \Delta of the entire rational system satisfies \Delta\le3r^{-1/4}. The number |B|+JN^2 of explicit columns and their binary lengths are polynomial, since r\le m.
Apply Equation (5.1). Write S for the augmented signed matrix, and distinguish the output signs \sigma_{j,k} from the fixed construction signs \tau_{j,k}. Its lower principal block is
The padding contribution to its upper principal block is exactly
If \|S\|\le T, then \|D_0\|\le T and \|VD_0V^T\|\le T. Subtracting the latter from the full upper block gives
No assertion about the signed off-diagonal block is needed.
For a fully rational certificate, choose a dyadic d_0 with \sqrt\Delta\le d_0\le2\sqrt\Delta by squared comparisons and set T=2^{15}d_0. Check TI-S\succeq0 and TI+S\succeq0 exactly by rational elimination. Since 40<2^{15}, the signing theorem guarantees that both tests pass. The certified output satisfies Equation (5.9) and T\le2^{16}\sqrt\Delta.
Return the positive data signs A=\{e:\sigma_e=1\}. By Equations (5.5) and (5.9), its centered half sum has norm at most
Thus one may take C_s=2^{20}. The rational PSD tests have polynomial cost and certify all the required matrix estimates simultaneously. The signing algorithm and all numerical routines above have prescribed polynomial precision and iteration bounds. This proves deterministic polynomial bit complexity.
6 Packing-preserving sparsification and the final tree
Lemma 6.1 (One sparsification step). For all sufficiently large integers r, from an explicit graph H containing r disjoint spanning trees one can construct a subgraph H'=(V(H),A) and an integer r' such that
for an absolute C_1. The construction is deterministic and takes polynomial bit time, with the certificate in Lemma 5.2.
Proof. Use Proposition 3.1 and discard excess trees to obtain a union B of q trees with (1-Ar^{-1/16})r\le q\le r. Increase the cutoff so q\ge r/2, and apply Lemmas 4.1 and 5.2. Put \epsilon_r=C_s r^{-1/8}. The two principal blocks of Equation (5.3) give
A centered cut indicator x has xx^T\in\mathcal N. By Equation (3.1), x^TXx\le3x^TL_Hx; evaluating the first inequality on x proves Equation (6.2).
For packing, fix a partition into d parts. Let W be the span of all z_e with endpoints in a common part, and let \Pi be the orthogonal projection onto W^\perp. Rank preservation from Lemma 4.1 gives \dim W\le\sum_{P\in\mathcal P}(|P|-1)=n-d, hence \rank\Pi\ge d-1. Taking the trace after projection in the second inequality of Equation (6.4), and then using Equation (4.1), gives
The integer packing criterion thus supplies at least
spanning trees in H'. Compute its maximum packing number, capped at \lfloor r/2\rfloor, by binary search with the constructive graphic-matroid union algorithm, and denote the result by r'. The lower bound in Equation (6.5) is already at most \lfloor r/2\rfloor, so capping does not reduce that guarantee. Consequently
for an absolute C_2, absorbing the floor loss 1/r, the extraction loss, and \epsilon_r. Taking a sufficiently large absolute cutoff gives Equation (6.1). Dividing a_r=\tfrac12(1+6\epsilon_r) by this lower bound and enlarging the absolute constant proves Equation (6.3).
Proof of Theorem 1.1 for explicit graphs. First suppose n\ge2. Put r_{\mathrm{init}}=\max\{1,\lfloor k/2\rfloor\}. For a partition into d\ge2 parts, summing the k-edge-connectivity bounds on its parts gives |E_G(\mathcal P)|\ge kd/2. Thus Equation (3.2) supplies \lfloor k/2\rfloor trees, and connectedness supplies one when k=1. Construct this initial packing. Notice that r_{\mathrm{init}}\ge k/3.
Starting with H_0=G and r_0=r_{\mathrm{init}}, apply Lemma 6.1 whenever the current parameter is at least the fixed absolute cutoff R_0. Write H_i,r_i for the resulting sequence. At termination 1\le r_J<R_0, and every H_i remains connected. Return any spanning tree of H_J.
The ratio estimate gives, for every cut,
Since r_{i+1}\le r_i/2, reading the parameters backwards bounds
Thus the product is bounded by one absolute constant, independently of the initial packing number. With r_J<R_0 and r_{\mathrm{init}}\ge k/3, the displayed estimate implies Equation (1.1) for a universal C. The same calculation covers J=0, with empty product one: in that case r_{\mathrm{init}}<R_0 and any spanning tree suffices.
There are at most J_{\max}=1+\lceil\log_2(m+1)\rceil iterations. Every iteration consists of deterministic polynomial-time routines, including the rational signing algorithm of Theorem A.1. The arithmetic and precision bounds proved above ensure that all intermediate encodings and the total work remain polynomial in the explicit input length. When n=1, return the empty tree before any packing or matrix call.
Binary multiplicities. It remains to reduce a succinct multigraph to an explicit one without work polynomial in the numerical value of k. For n\ge2, let c_{uv} be the binary multiplicity of the unordered pair uv and set
Every nontrivial cut still has c'-capacity at least k: either one crossing pair already contributes k, or no crossing multiplicity was changed. Rounding loses less than one per crossing pair, of which there are at most n^2/4. Consequently the explicit graph \widetilde G with multiplicities a_{uv} satisfies
Each a_{uv}\le2n^2 and there are fewer than n^2/2 pairs, so |E(\widetilde G)|<n^4. Apply the explicit algorithm with connectivity bound n^2. Its output tree is C/n^2-thin in \widetilde G, and hence 2C/k-thin in the original graph by Equation (6.7). Although temporary scaling can make a_{uv}>c_{uv}, a tree uses at most one edge of any parallel pair. Every selected pair has c_{uv}>0, so its tree edge maps to a genuine original edge. All arithmetic in Equation (6.6) is polynomial in \log k, the multiplicity encoding lengths, and n; the main routine uses the new parameter n^2. Enlarging the universal constant by two completes Theorem 1.1 in the binary model.
7 Simultaneous cost-and-cut rounding
The all-cut theorem also permits control of one nonnegative cost functional. The reduction combines the truncation and rounding in (6.6) with repeated deletion and selection of the least-cost tree, as in Oveis Gharan and Saberi [21, full preprint, Proposition 5.1]. The rational compression below keeps the auxiliary graph polynomial in the input bit length.
Corollary 7.1 (Thin and cheap rounding of fractional cuts). Fix once and for all an integer B\ge\max\{1,C\}, where C is the constant in Theorem 1.1. Let G=(V,E) be a finite undirected graph on n\ge2 vertices, given by an explicit list of edge records; in this corollary, loops and parallel records are allowed. Given nonnegative rational numbers x_e,c_e in binary, suppose that
There is a deterministic algorithm, polynomial in the total binary input length, that returns a spanning tree T\subseteq\{e\in E:x_e>0\} satisfying simultaneously
The cut inequalities are a promise on the input; no metric assumption on the costs is required.
Proof. Discard loops, which affect no cut and can only reduce the nonnegative cost sum. For each unordered nonloop pair p, let E_p be its set of edge records and put X_p=\sum_{e\in E_p}x_e. Discard pairs with X_p=0; otherwise choose an original edge e_p with x_{e_p}>0 of minimum cost among such edges, and put d_p=c_{e_p}. This preserves every cut mass and gives
Set K=n^2, y_p=\min\{X_p,1\}, and a_p=\lfloor2K y_p\rfloor. Form an explicit loopless multigraph A with a_p labelled copies of pair p, each of cost d_p. Every cut has y-mass at least one: if a crossing coordinate was truncated, that coordinate alone contributes one, and otherwise the cut mass is unchanged. A cut crosses at most n^2/4 unordered pairs, so rounding down loses at most n^2/4 from its scaled mass. Hence
Each a_p\le2n^2, and fewer than n^2/2 pairs occur, so |E(A)|<n^4. In particular, A is connected.
If K<12B, select any spanning tree of A. Its load on each cut is at most that of A, and its cost is at most c(A) by nonnegativity. Equation (7.4) and 2K<24B therefore give both asserted bounds, including when the cost sum is zero.
Suppose now that K\ge12B, and set k=\lfloor K/2\rfloor and m=\lfloor K/(6B)\rfloor. Starting with R_0=A, apply Theorem 1.1 with connectivity parameter k to R_i, obtain a tree T_i, and delete its labelled edges to form R_{i+1}, for 0\le i<m. To verify that every call is legal, inductively we have, for all cuts and 0\le i\le m,
Indeed, the second inequality follows from m\le K/(6B). Together with (7.3), it makes R_i k-edge-connected before its call. Since k\ge K/3, the returned tree obeys
which proves the next instance of (7.5). Equation (7.4) then makes every T_i at most 6B-thin relative to x. The trees are edge-disjoint in A, and m\ge K/(12B) because K/(6B)\ge2. Nonnegative costs therefore give
Select a least-cost T_i.
In either case, a selected tree uses at most one copy of any parallel pair. Replace that copy by e_p. The resulting original edges still form a spanning tree, have the same cut loads and cost, and all have positive x_e. Different extracted trees may lift to the same original edge, which is harmless because only one tree is output.
All pair sums, truncations, floors, and cost comparisons use exact rational or integer arithmetic of polynomial bit length; no common denominator is expanded into edge copies. The positive support is connected by the cut promise, so it contains at least n-1 distinct nonloop pairs. Thus even if n is encoded in binary, it is bounded by the length of the explicit input. There are O(n^2) calls on graphs with fewer than n^4 explicit edges and an O(\log n)-bit parameter k. Deleting labelled copies, summing and comparing tree costs, and lifting the selected tree are polynomial-bit operations. Very small positive coordinates may round to zero, but (7.3) preserves connectivity. No division by \sum_e c_ex_e occurs; if this sum is zero, c(A)=0 and the output cost is zero. This proves the stated bit bound and covers zero values.
The historical thin-and-cheap formulation. The author full manuscript of Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi defines an (\alpha,s)-thin tree for a point z in a spanning-tree polytope by the all-cut bound |\delta_T(S)|\le\alpha z(\delta(S)) and the cost bound c(T)\le s c(z), with \alpha\ge1. Its Conjecture 6.1 asks for absolute constants and a polynomial-time construction for every feasible Held–Karp solution [4, author full manuscript, Definition 4.1 and Conjecture 6.1].
For rational data on n\ge2 vertices in that paper’s directed-metric setting, let h be a feasible Held–Karp vector and use its normalized symmetrization
from equation (3.5) of the full manuscript. The feasibility calculation in the proof of its Lemma 3.1 puts z in the corresponding spanning-tree polytope [4, author full manuscript, equation (3.5) and proof of Lemma 3.1]. In particular, flow balance and the cut constraint give
For each support pair p=\{u,v\}, set d_p=\min\{c_{uv},c_{vu}\}, the cost of the cheaper of both orientations. Its induced fractional cost satisfies
Apply Corollary 7.1 with x=z and costs d_p. With the same cost function on the tree and the fractional point, the corollary gives c(T)\le24B c(z) and the required all-cut bound. It therefore supplies the two (24B,24B) inequalities on the undirected support, with deterministic polynomial-bit construction for rationally encoded data. The cheaper orientation of a selected pair need not have positive h-value; the support requirement is z_p>0. More generally, every rational point in a spanning-tree polytope satisfies the cut promise, since each constituent spanning tree meets every nontrivial cut. The bit guarantee here is not a claim for arbitrary real-oracle inputs.
The earlier SODA version instead fixes an optimum Held–Karp solution and defines its cost bound as c(T)\le s\,OPT_{\rm HK} in Definition 5.1; its Theorem 6.1 is the tour-augmentation theorem, not the full-manuscript conjecture [3, Definition 5.1 and Theorem 6.1]. Constant-factor approximation for ATSP was already established independently by Svensson, Tarnawski, and Végh and improved by Traub and Vygen [23, 25]. The consequence proved here concerns the underlying simultaneous rounding formulation; no new approximation-order claim is made.
A A finite-bit signing interface
We record a conservative quantitative form of the rank-one signing method of Ezeunala and Jiang [9]. The constants below suffice for the exact padding argument. We include their accounting and the finite-precision implementation to make the input interface explicit.
Theorem A.1 (Rational rank-one signing). Given rational Hermitian matrices H_1,\ldots,H_N of rank at most one, a deterministic algorithm returns signs \sigma_i\in\{-1,1\} such that
Its running time is polynomial in the total binary encoding length. Consequently, for rational columns v_i with \sum_i v_iv_i^*=I, the same algorithm gives discrepancy at most 40\sqrt{\max_i\|v_i\|^2}.
The last assertion follows from (v_iv_i^*)^2=\|v_i\|^2v_iv_i^* and positivity. Forming the outer products has polynomial bit cost. We prove the matrix assertion next.
A.1 The potential and its quantitative estimates
In dimension zero, any signs suffice. Otherwise discard zero matrices; if none remain, any signs again suffice. A nonzero rank-one Hermitian matrix has one nonzero eigenvalue, equal to its trace. With D=\sum_i|\operatorname{Tr}H_i|, put
These are rational positive semidefinite matrices and \sum_i\operatorname{Tr}A_i=1. Matrix Cauchy–Schwarz gives 1/(Nd^2)\le\nu_0\le1, where d is the matrix order. Rational positive-semidefiniteness tests and bisection compute rational parameters
Set c=384, K=100, and \sigma=\lambda^2/\nu. Thus \varepsilon\ge1/(Nd^3) and 1/(40000N^2)\le\sigma\le1/(10000N^2).
For x\in[-1,1]^N, let
Define R(x) as the minimum of t+\varepsilon\operatorname{Tr}(X+Y) over X,Y\succ0 subject to
and put \Psi(x)=R(x)+\lambda\sum_i\psi_i.
The variational argument of Ezeunala and Jiang [9, Section 4.1] uses only c>0 and gives
For clarity, its quantitative ingredients are as follows. The minimizer is unique; with its positive definite dual multipliers P,Q it satisfies
and both inequalities in (A.1) are tight. Indeed, the scalar choice X=Y=aI proves the upper bound in (A.2); its value is below 42<K. On the sublevel set of objective at most K, the constraints bound the inverse matrices and the trace penalty bounds X,Y. Compactness gives attainment. Stationarity gives (A.3); positive dual multipliers imply tightness. Strict convexity of \operatorname{Tr}(PX^{-1})+\operatorname{Tr}(QY^{-1}) gives uniqueness.
On pairs of Hermitian matrices define
The positive-map argument of [9, Claim 4.1] yields the following bound, with the Frobenius norm specified explicitly:
All operator norms on spaces of matrix pairs here are induced by the Frobenius norm. To verify the norm bound, write \mathcal L=\mathcal C(I-\mathcal T), where
Both \mathcal T and \mathcal C^{-1} preserve positive semidefinite matrix pairs. The dual identities give
Since all four matrices are positive definite, there is a \delta>0 such that the right side is at most (1-\delta)(P,Q) in componentwise Loewner order. Thus \mathcal T is a strict contraction in the norm
The convergent series \mathcal L^{-1}=\sum_{j\ge0}\mathcal T^j\mathcal C^{-1} is positive. Its value on (I,I) is (P,Q)/\varepsilon\preceq(I,I)/\varepsilon. Consequently its induced norm for \|(U,V)\|_{\max}=\max\{\|U\|_{\op},\|V\|_{\op}\} is at most \varepsilon^{-1}. Finally, \mathcal L and its inverse are self-adjoint for the Frobenius pairing. The Frobenius operator norm of \mathcal L^{-1} therefore equals its spectral radius, which is bounded by every induced norm. This proves (A.4).
The Hessian \mathcal H of the Lagrangian in (X,Y) satisfies
The lower bound follows by substituting P\succeq\varepsilon X^2 in 2\operatorname{Tr}(PX^{-1}UX^{-1}UX^{-1}) and using X^{-1}\succeq(\varepsilon/K)I; the other block is identical. The upper bound uses three inverse factors of norm at most 2K in each of the two terms of a Hessian block.
A.2 A quantified direction of decrease
A coordinate is active when |x_i|<1; let n be their number. In the following differential calculations, vectors and derivatives are restricted to these coordinates, with the other coordinates fixed on the current open face. Write A_i=u_iu_i^* in this analysis and set
The factors u_i need not be rational: the algorithm below uses only the rational matrices A_i. If c\psi_i b_i\ge1-x_i, moving x_i to 1 preserves feasibility in (A.1) with the same (t,X,Y) and decreases \Psi by at least \lambda\psi_i. The symmetric condition c\psi_i a_i\ge1+x_i permits the move to -1. We may therefore assume
Put \alpha_i=1+c\psi_i'b_i, \beta_i=1-c\psi_i'a_i, and
For k_i=-\psi_i'', elementary substitution in (A.6) gives
Here is a direct check. By symmetry take x_i\ge0 and put r=1-x_i^2. Then 2/3\le\alpha_i\beta_i\le2/r and k_i=(2/3)r^{-5/3}(1+x_i^2/3). Also \widetilde a_i\widetilde b_i=\psi_i a_i b_i \le r^{2/3}/c^2. For u=c\psi_i a_i/(1+x_i) and v=c\psi_i b_i/(1-x_i) in (0,1),
Maximizing the first in u and minimizing v, and maximizing the second in u,v, bounds them by 3 and 1. For negative x_i the roles interchange. These formulas also prove the remaining assertions of (A.7).
We quantify the covariance construction in [9, Lemma 4.5]. Define the real symmetric, entrywise nonnegative positive semidefinite matrices
and D_F=\operatorname{diag}(\widetilde a_i z_i), D_G=\operatorname{diag}(\widetilde b_i w_i). The dual identities give \mathsf A w\le z and \mathsf Bz\le w coordinatewise. Moreover,
For example, \mathsf A_{ij}^2\le c\widetilde a_i\widetilde a_j\mathsf A_{ij} and \widetilde a_i\widetilde b_i\le c^{-2} bound the first sum by c^{-1}\sum_j(\mathsf A w)_j/z_j.
Restrict D_F^{1/2}F and D_G^{1/2}G to right singular directions with singular value at most 1/2 for these two maps. Each restriction has codimension at most 4n/c. Impose also (I-\mathsf A)F+(I-\mathsf B)G=0. The resulting subspace \mathcal G\subseteq\mathbb R^{2n} has dimension at least n-8n/c. The covariance theorem of Bansal and Garg [6, Theorem 6], in the form stated by Bansal [5, Theorem 2.5] and recalled in [9, Lemma 2.1], supplies a positive semidefinite \Gamma with
Take a centered finitely supported (F,G) with covariance \Gamma and set H=F-\mathsf BG=\mathsf AF-G, h_i=H_i/T_i, and \omega_i=\mathbb E H_i^2. The two singular-value restrictions give
The response matrices are \dot X=X(\sum_i\ell_iF_iA_i)X and \dot Y=Y(\sum_i m_iG_iA_i)Y. The diagonal of their inversion-energy quadratic form
is (D_F,D_G). Hence
We expand the first and second variation calculation of [9, Lemma 4.3 and its proof] to obtain
The first identity is the envelope formula \partial_iR=\alpha_i p_i-\beta_i q_i. For the second, keep t fixed and replace x by x+\tau h. Invertibility of \mathcal L and the implicit function theorem give a local curve (X(\tau),Y(\tau)) satisfying both tight constraints. Its first derivatives are the response matrices above: the identities H=F-\mathsf BG=\mathsf AF-G verify the linearized constraints. This curve stays positive definite for small \tau, and its objective bounds R(x+\tau h) from above with equality at \tau=0. Differentiating twice and pairing with P,Q, using \mathcal L(P,Q)=\varepsilon(I,I), therefore gives
Write E_X,E_Y for the two summands of E_h. Since P\succeq X\eta_x(Q)X,
The inequality |u_i^*\dot X u_i|^2\le a_i u_i^*\dot X X^{-1}\dot X u_i and weighted Cauchy–Schwarz bound the X mixed sum by
The corresponding Y bound uses B_Y=c\sum_i(\psi_i')^2\psi_i^{-1}h_i^2b_ip_i. Thus the full mixed term is at most 2\sqrt{E_hB_h}, where B_h=B_X+B_Y. Finally, (\psi_i')^2/(\psi_i k_i)\le1/2 gives B_h\le(c/2)\sum_i k_i h_i^2(b_ip_i+a_iq_i), and 2\sqrt{E_hB_h}\le E_h+B_h proves the asserted Hessian bound.
Let \Sigma=\mathbb E hh^T and choose \mu_i=-24T_i^{-1}(\widetilde a_i-\widetilde b_i)\omega_i. Using (A.7) and (A.8), the operator \mathcal Df=\nabla f\cdot\mu+\tfrac12\operatorname{Tr}(\nabla^2f\Sigma) satisfies
The first line uses cancellation of 24\sum_i(\widetilde a_i z_i+\widetilde b_i w_i)\omega_i by the drift. For the second, the identity T_i(\widetilde a_i+\widetilde b_i)=a_i+b_i and (A.6) give |\psi_i'\mu_i|\le(48/c)k_i\omega_i/T_i^2.
All movement bounds are polynomial and uniform in the state. Indeed (A.3) gives
The spectral radius of \mathsf A\mathsf B is at most (1-s_0)^2. Using its positive semidefinite conjugate yields
Solving the two response equations gives \|F\|^2+\|G\|^2\le E_0\|H\|^2, where E_0=2J^2(1+3N)^2. Consequently, with
we have \sum_i\omega_i\ge n/C_1, \omega_i\le C_1 and
This proves a quantitative descent alternative for c=384. The covariance and drift are used only to prove that a direction of decrease exists. The algorithm below computes neither of them nor the possibly irrational spectral subspaces used in their construction.
Here is the deterministic alternative that the algorithm will use. Suppose at least one coordinate is active, every active coordinate is farther than \sigma from its endpoints, and put a=\lambda/(8C_0^2). Either an endpoint test above succeeds, giving a decrease of at least \lambda\sigma, or
The endpoint estimate uses \psi_i\ge\sigma. If all endpoint tests fail, (A.6) holds and the preceding calculation applies. If also \|\nabla\Psi\|_\infty<a, then \nabla\Psi\cdot\mu\ge-aC_0n, whereas \mathcal D\Psi\le-\lambda n/C_0=-8aC_0n. Hence
Together with \operatorname{Tr}\Sigma\le C_0n, this gives a Hessian eigenvalue at most -14a, and therefore the asserted -8a bound. The remaining task is to find one of these decreases using rational value queries.
A.3 Uniform derivatives and a rational value oracle
We next make the descent computable. On any open face, let z=(t,X,Y,P,Q) and write its tight constraints and stationarity equations as F(x,z)=0. The source’s smoothness proof [9, Section 4.1] applies to our parameters. Here we record a uniform quantitative bound. Write B=\mathcal L^{-1} and E=(I,I). An inhomogeneous linearized system has the form
Eliminating u,p determines h with denominator \langle BE,\mathcal HBE\rangle. By (A.4), BE=(P,Q)/\varepsilon; thus
The last inequality uses \|P\|_F^2+\|Q\|_F^2\ge1/(2d). The upper bound uses \operatorname{Tr}(P+Q)=1 and positivity. Back substitution in the three equations and (A.4)–(A.5) bound the complete Jacobian inverse by a constant times (d+1)(1+\varepsilon^{-1})^4.
When every active coordinate is at least \sigma/2 from its endpoints, the first three derivatives of \psi_i are bounded by 100(2/\sigma)^3. All derivatives of F through order three are therefore bounded by a computable polynomial in N,d,\varepsilon^{-1},\sigma^{-1}. Three implicit differentiations give a uniform polynomial bound M\ge1 for both \|\nabla^2\Psi\| and \|\nabla^3\Psi\| on these strips. There is no dependence on the number of faces. For an explicit choice, let
The product rule, the inverse bound 2K, and Frobenius product inequalities verify these deliberately loose bounds.
A value of \Psi to additive accuracy \eta>0 is computable in polynomial time in the input length and \log\eta^{-1}. Approximate every \psi_i by a nonnegative rational in [0,1] to error \delta. This changes the optimal value by at most (cKd+\lambda N)\delta: in either direction, increase t by cKd\delta to absorb the perturbation of the matrix constraints. Indeed, \sum_iA_i^2\preceq\nu I and \|Y\|\le K/\varepsilon bound the change in \eta_x(Y) by c\delta\nu\|Y\|\le c\delta\nu K/\varepsilon=cKd\delta; the other block is identical. The resulting rational program is a semidefinite program by the Schur-complement formula. Impose the rational bounds
The scalar upper bound and sublevel estimates hold for every coefficient vector in [0,1]^N, so these boxes contain the minimizers both before and after approximation. The preceding comparison of unboxed optimal values therefore applies to the boxed programs as well. The point X=Y=I/20, t=50 has constraint slack at least 50-20-2-384/20=8.8 and lies strictly inside the bounds. It supplies an inverse-polynomial interior radius: each Schur block dominates \left(\begin{smallmatrix}28.8I&I\\I&0.05I\end{smallmatrix}\right) \succeq I/100, since subtracting I/100 leaves the scalar determinant 28.79\cdot0.04-1=0.1516>0. In upper-triangular real and imaginary coordinates, a ball of radius 10^{-6} preserves this margin and all the boxes: a matrix-pair perturbation changes either Schur block by at most |\Delta t|+384\|\Delta Y\|_F+\|\Delta X\|_F or its symmetric counterpart. An outer radius 400(d+1)/\varepsilon suffices. Rational weak optimization [12] therefore evaluates the rational program to error \eta/2 in polynomial work. Choosing \delta\le\eta/[2(cKd+\lambda N)] gives the claimed oracle. Rational bisection computes the cube roots. This value oracle also works on lower-dimensional faces and at vertices.
A.4 Rational descent and termination
At the start of an iteration, move every active coordinate at distance z\le\sigma from its nearest endpoint to that endpoint. This never increases the exact potential, since
There are at most N such permanent freezes. Every remaining active coordinate is more than \sigma from either endpoint. If none remain, return the resulting vertex; all derivative and direction computations below are performed only when n\ge1.
With a=\lambda/(8C_0^2) as above, choose positive powers of two s,h, each within a factor two below its indicated bound, with
Central first differences, central diagonal second differences, and four-corner mixed second differences of the value oracle, each query to error at most ah^2/(128N), give rational approximations \widehat g,\widehat H to \nabla\Psi,\nabla^2\Psi satisfying
Taylor’s theorem and the third-derivative bound prove these estimates; all stencil points stay in the \sigma/2 strips.
Consider all 2n single-coordinate endpoint moves and the coordinate move x-s\operatorname{sign}(\widehat g_i)e_i, where |\widehat g_i| is maximal. Test the rational matrix \widehat H+7aI for positive semidefiniteness by exact elimination. If it fails, elimination supplies a nonzero rational vector of negative quadratic form. Set \beta=a/(4096M) and \tau=a/(1024M) and normalize that vector, using a rational upper approximation to its norm, to obtain w with 1-\beta\le\|w\|\le1. Its Rayleigh quotient for \widehat H is strictly below -7a. Choose \rho as the largest dyadic power at most sa/(4096MN); it divides the dyadic s. Round s(1-\tau)w to \rho\mathbb Z^n to obtain q. The rounding error is at most \sqrt n\rho/2\le s\tau/8, so \|q\|\le s and \|q-sw\|\le9s\tau/8. The negative-direction certificate and the Hessian error bound give
In particular,
Include both x+q and x-q. If the positive-semidefiniteness test passes, omit these two candidates. Whenever \lambda_{\min}(\nabla^2\Psi)\le-8a, the test necessarily fails, so a curvature candidate is available when it is needed. The two displacements are exact negatives, so their linear Taylor terms cancel.
By (A.10), one candidate decreases the true potential by at least 2\Delta. An available endpoint move gives a decrease at least \lambda\sigma\ge2\Delta. In the remaining case, if \|\nabla\Psi\|_\infty\ge a, the selected coordinate has the correct sign and derivative magnitude at least 3a/4, giving decrease at least (3/4)as-Ms^2/2\ge(5/8)as\ge(5/2)\Delta. Otherwise (A.10) gives \lambda_{\min}(\nabla^2\Psi)\le-8a; averaging the two curvature candidates gives decrease at least 3as^2-Ms^3/6>2\Delta. Evaluate all final candidates to error \Delta/4 and choose the smallest reported value. Selection loses at most \Delta/2 against the best true candidate. Every accepted step thus decreases the exact potential by at least 3\Delta/2.
Starting from x=0, every live coordinate stays on the fixed mesh \rho\mathbb Z; frozen coordinates equal \pm1. All coordinates, parameters, and query points have polynomial encoding length. There are at most \Psi(0)/\Delta main iterations, each with polynomially many rational semidefinite value queries and one exact rational positive-semidefiniteness test. The normalized lower bounds on \nu, \varepsilon, \lambda, and \sigma imply that C_0 and M are bounded by fixed polynomials in N+d. In turn, a and the chosen s,h are bounded below by fixed inverse polynomials, as is \Delta=as^2. Since \Psi(0)<40, the iteration count is polynomial as well. Together with the encoding and oracle bounds, this proves deterministic polynomial bit complexity on every execution.
At the final vertex x^f, the coordinate term vanishes and (A.2) gives
Undoing the rational normalization and folding the signs of the original traces into x_i^f proves Theorem A.1.
References
- [1]Nima Anari and Shayan Oveis Gharan. Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. arXiv:1411.4613v4, 2015. Full version, revised 1 September 2015. arXiv:1411.4613v4, https://arxiv.org/abs/1411.4613v4.
- [2]Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander Flows, Geometric Embeddings and Graph Partitioning. Journal of the ACM, 56(2):5:1–5:37, 2009. doi:10.1145/1502793.1502794.
- [3]Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi. An O(\log n/\log\log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM–SIAM Symposium on Discrete Algorithms, pages 379–389, SIAM, 2010. SODA version; its definition and theorem numbering differs from the author full manuscript. doi:10.1137/1.9781611973075.32.
- [4]Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi. An O(\log n/\log\log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Operations Research, 65(4):1043–1061, 2017. Preliminary version in SODA 2010. Full-manuscript locators refer to the author full manuscript formerly hosted at NYU Stern (Definition 4.1 and Conjecture 6.1; link unavailable). doi:10.1287/opre.2017.1603.
- [5]Nikhil Bansal. On a Generalization of Iterated and Randomized Rounding. Theory of Computing, 20(6):1–23, 2024. doi:10.4086/toc.2024.v020a006.
- [6]Nikhil Bansal and Shashwat Garg. Algorithmic Discrepancy Beyond Partial Coloring. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 914–926, 2017. Full version: arXiv:1611.01805v2, Theorem 6. doi:10.1145/3055399.3055490, arXiv:1611.01805.
- [7]Franck Barthe. On a reverse form of the Brascamp–Lieb inequality. Inventiones Mathematicae, 134(2):335–361, 1998. doi:10.1007/s002220050267, arXiv:math/9705210.
- [8]Jack Edmonds. Matroid Partition. In George B. Dantzig and Arthur F. Veinott, Jr., editors, Mathematics of the Decision Sciences, Part 1, pages 335–345, American Mathematical Society, 1968. Reprinted in 50 Years of Integer Programming 1958–2008, Springer, 2010, pp. 199–217, doi:10.1007/978-3-540-68279-0_7. https://link.springer.com/chapter/10.1007/978-3-540-68279-0_7.
- [9]Ekene Ezeunala and Haotian Jiang. Rank-One Matrix Discrepancy and Algorithmic Kadison–Singer. arXiv:2609.17266v1, 2026. arXiv:2609.17266v1, https://arxiv.org/abs/2609.17266v1.
- [10]Maurice Fréchet. Les dimensions d’un ensemble abstrait. Mathematische Annalen, 68(2):145–168, 1910. doi:10.1007/BF01474158.
- [11]Luis A. Goddyn. Some Open Problems I Like. 2004. Problem 4; webpage modified March 17, 2004. https://web.archive.org/web/20211025204852/https://www.sfu.ca/~goddyn/Problems/problems.html.
- [12]Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics 2, Springer, 1988. doi:10.1007/978-3-642-97881-4.
- [13]Nicholas J. A. Harvey and Neil Olver. Pipage Rounding, Pessimistic Estimators and Matrix Concentration. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 926–945, Society for Industrial and Applied Mathematics, 2014. Full version: arXiv:1307.2274v1, Appendix F. doi:10.1137/1.9781611973402.69, arXiv:1307.2274.
- [14]Tomáš Kaiser. A short proof of the tree-packing theorem. Discrete Mathematics, 312(10):1689–1691, 2012. doi:10.1016/j.disc.2012.01.020, arXiv:0911.2809v3.
- [15]Nathan Klein and Neil Olver. Thin Trees for Laminar Families. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, pages 50–59, IEEE, 2023. doi:10.1109/FOCS57990.2023.00011, arXiv:2304.07674.
- [16]Nathan Klein, Neil Olver, and Zi Song Yeoh. Thin Trees for near Minimum Cuts. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), pages 129:1–129:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. doi:10.4230/LIPIcs.ICALP.2026.129, arXiv:2605.12669.
- [17]Casimir Kuratowski. Quelques problèmes concernant les espaces métriques non-séparables. Fundamenta Mathematicae, 25(1):534–545, 1935. doi:10.4064/fm-25-1-534-545.
- [18]Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava. Interlacing Families II: Mixed Characteristic Polynomials and the Kadison–Singer Problem. Annals of Mathematics, 182(1):327–350, 2015. doi:10.4007/annals.2015.182.1.8.
- [19]C. St. J. A. Nash-Williams. Edge-Disjoint Spanning Trees of Finite Graphs. Journal of the London Mathematical Society, s1-36(1):445–450, 1961. doi:10.1112/jlms/s1-36.1.445.
- [20]OpenAI. The strong thin tree conjecture. OpenAI Math Release preprint PDF, 2026. Reading view on this site: The strong thin tree conjecture.
- [21]Shayan Oveis Gharan and Amin Saberi. The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus. In Proceedings of the Twenty-Second Annual ACM–SIAM Symposium on Discrete Algorithms, pages 967–975, SIAM, 2011. Theorem numbers refer to the full preprint, arXiv:0909.2849. doi:10.1137/1.9781611973082.75, arXiv:0909.2849.
- [22]I. J. Schoenberg. Remarks to Maurice Fréchet’s Article “Sur la définition axiomatique d’une classe d’espace distanciés vectoriellement applicable sur l’espace de Hilbert”. Annals of Mathematics, 36(3):724–732, 1935. doi:10.2307/1968654.
- [23]Ola Svensson, Jakub Tarnawski, and László A. Végh. A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Journal of the ACM, 67(6):37:1–37:53, 2020. Preliminary version in STOC 2018. doi:10.1145/3424306, arXiv:1708.04215.
- [24]Tatsuya Terao. Faster Matroid Partition Algorithms. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 104:1–104:20, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ICALP.2023.104.
- [25]Vera Traub and Jens Vygen. An Improved Approximation Algorithm for the Asymmetric Traveling Salesman Problem. SIAM Journal on Computing, 51(1):139–173, 2022. Preliminary version in STOC 2020. doi:10.1137/20M1339313, arXiv:1912.00670.
- [26]W. T. Tutte. On the Problem of Decomposing a Graph into n Connected Factors. Journal of the London Mathematical Society, s1-36(1):221–230, 1961. doi:10.1112/jlms/s1-36.1.221.