Logarithmic Embeddings into Probabilistic Spanning Trees for Distances and Capacities

Introduction

Approximating a graph by a distribution of trees is a basic tool in the design of algorithms. A tree makes distances, cuts, and routing particularly simple, while a distribution can avoid the distortion forced on any one tree. There are, however, two different notions of a tree approximation. An abstract tree metric may introduce Steiner vertices and edges unrelated to the input graph. A spanning tree must use the original vertices and original edges, with their given lengths. The latter restriction is essential when a tree path must be a path in the network itself.

Alon, Karp, Peleg, and West [5, 6] formulated the spanning-tree problem as a zero-sum game between a tree player and an edge player. Their extended abstract appeared at the 1991 DIMACS Workshop on On-Line Algorithms, with proceedings published in 1992; the full paper appeared in 1995. They proved a bound of $\exp(O(\sqrt{\log n\log\log n}))$ and conjectured an $O(\log n)$ bound. Their original payoff differs pointwise by at most one from $d_{T,\ell}(u,v)/\ell_{uv}$, so the two game values differ by at most one. The modified game asks for a distribution over spanning trees whose expected stretch is small on every original edge. An edge guarantee immediately extends to every pair of vertices by summing along a shortest graph path.

Subsequent work brought the upper bound close to logarithmic. Elkin, Emek, Spielman, and Teng [13] obtained average stretch $O(\log^{2} n \log\log n)$. Abraham, Bartal, and Neiman [2] obtained stochastic stretch $O(\log n\log\log n(\log\log\log n)^{3})$. The petal decomposition of Abraham and Neiman [7] gives average stretch $O(\log n\log\log n)$ and a construction with the same logarithmic factors in its nearly linear running time. Low-stretch trees also underlie preconditioners for fast solvers of symmetric diagonally dominant linear systems [23]. The remaining gap is a geometric one: local partitions must be chosen so that they can be reconnected using original edges without losing the distance estimate.

We close this gap by proving the logarithmic bound for spanning trees. The theorem is weighted: the demand assigned to an edge is independent of its length. This is the form needed both for the spanning-tree game and for a capacity decomposition. Our construction runs in polynomial time for arbitrary rational input. Its running time is not nearly linear; the contribution is the logarithmic approximation within the spanning-tree family and an explicit polynomial construction.

Results

Let $G=(V,E)$ be a connected undirected graph, with $n=|V|\ge2$ and $m=|E|$. Throughout the paper, a spanning tree has vertex set $V$ and uses only edges of $G$. For lengths $\ell_e>0$, write $d_{G,\ell}$ and $d_{T,\ell}$ for graph and tree distances. For capacities $c_e>0$ and a tree edge $f$, let $S_{T,f}$ be either component of $T-f$. Define

Thus the tree topology is a subgraph, while its capacities are determined by its fundamental cuts. These are exactly the smallest capacities on that topology that dominate every graph cut (Proposition 9.5).

Each distribution can be supported on at most $m$ trees. For rational input and rational $\vartheta$, it can be constructed deterministically using at most

weighted-tree calls and polynomial additional work. The complete running time is polynomial in the binary input length and $1/\vartheta$.

The capacity distribution is fixed before the cut or the demand vector is chosen. Its guarantee is $\max_f \mathbb{E}[L_T(f)/c_f]$, and the routing uses the fractional mixture of tree paths. The theorem does not require each sampled tree to have small congestion. The distance and capacity distributions may differ; this is necessary even when all graph lengths and capacities are one (Proposition 10.4).

The main ingredient is a deterministic weighted-tree theorem. Given arbitrary demands $a_e \ge0$ and lengths $\ell_e > 0$, it constructs a spanning tree satisfying

The geometric and entropy arguments proving this statement occupy § 4–§ 6. We use symbolic constants there and give an explicit admissible choice, including $C_0$, in § 11. The distribution construction in § 8 works with any weighted response bound $\rho$, loses only a factor $1+\vartheta$, and has a call bound independent of the numerical size of $\rho$.

Tightness on diamonds. The logarithmic lower bound for probabilistic tree metrics on recursive diamonds is classical [18]. We give a direct spanning-tree proof in § 10.1. For every spanning tree of the height-$k$ unit diamond $D_k$, the sum of tree distances over the $4^k$ original edges is at least $k4^k/9$. The same inequality, by double counting, gives an $\Omega(\log n)$ lower bound for maximum expected fundamental-cut congestion. Summing singleton tree cuts gives the lower bound for expected cut distortion as well. Thus all three logarithmic bounds in Theorem 1.1 are asymptotically tight on the same series-parallel family.

The size of an explicit decomposition. Charikar, Chekuri, Goel, Guha, and Plotkin [10] showed that $O(n\log n)$ abstract tree metrics suffice for their probabilistic metric embedding. This raises the corresponding support question for spanning trees. Our support bound $m$ cannot in general be replaced by $O(n\log n)$ for fundamental-cut congestion, even when the optimal congestion approaches one. For an integer $k \ge2$, let $G_k$ consist of two $k$-vertex stars whose edges have capacity $k^2$, together with all $k^2$ cross edges of capacity one.

The proof is in § 10.2. Since $n = 2k$ and $m = k^{2} + 2k - 2$, the theorem gives $\Omega(m/\rho)$ support. In particular, constant congestion can require $\Theta(m)$ trees, and logarithmic congestion can require $\Omega(n^{2}/\log n)$ trees. The lower bound concerns individual original-edge loads, the property used by the oblivious routing guarantee. It does not follow from cut approximation alone. At the attainable bound $\rho= \beta_k = 1 + O(1/n)$, every distribution needs at least $m - O(n) = (1 - o(1))m$ trees (Corollary 10.3). Thus the dependence on $m$ is asymptotically sharp for congestion tending to one.

Related work

Probabilistic metric embeddings. Bartal [8 Bar98] established probabilistic approximation by hierarchically well-separated trees (HSTs), first with distortion $O(\log^{2} n)$ and then with distortion $O(\log n \log\log n)$. Fakcharoenphol, Rao, and Talwar [16] obtained the optimal $O(\log n)$ bound: every finite metric admits a distribution of dominating tree metrics with this expected distortion for every pair. Their construction also produces HSTs, whose edge lengths decrease geometrically along root-to-leaf paths. The distinction between deterministic domination and expected distortion is central to the applications. A fixed feasible solution has a cost controlled in expectation by linearity, while domination supports transferring a tree solution back to the original metric. The allowed trees can have Steiner vertices and edges outside the input graph. Replacing such edges by graph paths can create cycles; extracting a spanning tree from their union need not preserve the distance bound. Consequently the metric theorem does not supply the original-edge guarantee studied here.

Approximation and online algorithms. Metric labeling illustrates the role of HST structure. Kleinberg and Tardos [20] give a constant-factor algorithm when the metric on the $k$ labels is an HST with a fixed separation greater than two. Combined with FRT, this yields an $O(\log k)$ approximation for arbitrary label metrics: assignment costs are unchanged, and the metric controls the pairwise separation costs. The related 0-extension problem fixes the labels of designated terminals. Calinescu, Karloff, and Rabani [11] obtain an $O(\log k)$ approximation, where $k$ counts terminals, through a metric relaxation and randomized partitions. Their partitioning method is also an ingredient in the development of FRT [16]; this is a connection between the techniques, rather than an attribution of the 0-extension theorem to FRT.

For network design, Awerbuch and Azar [1] use tree embeddings for uniform buy-at-bulk, where cable types and their costs per unit length are common to all edges. Their constant-factor tree algorithm and the FRT distortion bound give an $O(\log n)$ expected approximation, including the multiple source–sink setting. For group Steiner tree with $k$ groups, Garg, Konjevod, and Ravi [17] obtain an $O(\log n\log k)$ approximation on trees; combining it with FRT gives an $O(\log^{2} n\log k)$ on general graphs. In online computation, Fiat and Mendel [15] give an $O(\log n\log\log n)$-competitive algorithm on HSTs. Its classical combination with FRT gives an $O(\log^{2} n\log\log n)$ randomized competitive ratio for metrical task systems against oblivious adversaries [16]. These examples explain why both the distortion and the structure of the target trees matter: the reduction must preserve the particular objective and feasibility conditions of its application.

Spanning trees and numerical algorithms. The original-edge problem has a separate history, beginning with the tree edge game of Alon, Karp, Peleg, and West [6], motivated by the $k$-server problem on road networks. Their reduction relates the game value to a randomized competitive ratio against an oblivious adversary. The subsequent star decompositions of Elkin, Emek, Spielman, and Teng [13], the portal highways of Abraham, Bartal, and Neiman [2], and the petal decompositions of Abraham and Neiman [7] successively improved the distortion while maintaining a spanning subgraph. The latter construction achieves $O(\log n \log\log n)$ average stretch in $O(m\log n\log\log n)$ time. For unweighted series-parallel graphs, Emek and Peleg [14] already obtain a tight logarithmic distribution over spanning trees. The diamond lower bound of Gupta, Newman, Rabinovich, and Sinclair [18] therefore holds even in a graph class where the spanning-tree question was previously settled.

Low-stretch spanning trees also enter combinatorial preconditioning. Spielman and Teng [23] construct sparse subgraph preconditioners by adding edges to low-stretch trees and use recursive preconditioning to solve symmetric diagonally dominant systems in nearly linear time. This application requires efficient construction, in addition to a stretch bound. Our polynomial-time weighted oracle establishes the logarithmic distortion guarantee; obtaining a comparable running time remains a separate algorithmic question.