PaperlayerView exact revision on arXiv

Source-linked AI summary

Nearly Tight Low Stretch Spanning Trees

Ittai Abraham, Yair Bartal, Ofer Neiman

arXiv:0808.2017v1cs.DScs.DM

TL;DR

The paper addresses how to obtain low expected stretch in spanning trees, where earlier upper bounds left room for improvement. It combines recursive star decompositions with portal highways and a strong-diameter probabilistic decomposition, and gives a polylogarithmically tight upper bound on stretch(n).

  • Problem

    Earlier work had an upper bound of O((log n)^2 log log n), while the paper seeks a tighter upper bound on spanning-tree stretch(n).

    Source: §1 · p. 1

  • Method

    The paper combines recursive star decompositions and queue-based portal highways with a strong-diameter probabilistic decomposition theorem.

    Source: §1.1 · p. 2, §2 · p. 4, §3 · p. 12

  • Results

    O(log n log log n (log log log n)^3) is the paper’s tighter upper bound on stretch(n), tight up to polylogarithmic factors.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The result may improve the running time of the Spielman–Teng solver for sparse symmetric diagonally dominant linear systems.

    Source: §1 · p. 1

Abstract

from arXiv · show

We prove that any graph $G$ with $n$ points has a distribution $\mathcal{T}$ over spanning trees such that for any edge $(u,v)$ the expected stretch $E_{T \sim \mathcal{T}}[d_T(u,v)/d_G(u,v)]$ is bounded by $\tilde{O}(\log n)$. Our result is obtained via a new approach of building ``highways'' between portals and a new strong diameter probabilistic decomposition theorem.

1 Introduction

The paper improves upper bounds on spanning-tree stretch, using star decompositions, portal highways, and a strong-diameter decomposition theorem. It also describes applications to sparse linear-system solvers and communication-cost spanning trees.

1 Introduction

  • O(log n log log n (log log log n)^3) is the paper’s tighter upper bound on stretch(n), tight up to polylogarithmic factors.The paper first presents a slightly weaker bound and proves the tighter one in Appendix B.Source: §1 · p. 1

1.1 Techniques

  • A queue-based highway construction in recursive star decompositions targets low tree distances from the center, with radius stretch O(log log n).The queue prioritizes earlier points; choosing the first portal edge on a shortest path preserves the original distance to the first point.Source: §1.1 · p. 2
  • The paper develops a strong-diameter hierarchical decomposition for star decompositions, with expected edge-separation cost O(log n log(1/ε)/ε).Its analysis defines local growth rates in the changing graph and shows their expected sum across scales telescopes to n.Source: §1.1 · p. 3

1.2 Applications

  • The paper improves a bound over by roughly an additional O(log log n) factor and yields an O(log n log log n (log log log n)^3) approximation ratio for minimum communication-cost spanning trees.For planar graphs, it obtains an O(n log^2 n) bound.Source: §1.2 · p. 3

1.3 Structure of the Paper

  • The paper outlines a framework for constructing bounded-diameter trees, a distribution over star partitions for expected stretch analysis, and appendices on weighted graphs and the tighter bound.The main text proves stretch(n) = O(log n (log log n)^2 log log log n).Source: §1.3 · p. 3

2 Highways

This section develops and analyzes highway constructions using ordered queues and recursive star partitions to control root-to-point distances and radius stretch. It establishes bounds for the resulting hierarchical-star-partition tree and a single spanning tree, with analysis that limits fat-queue size and adapts cone-cutting.

2 Highways

  • Ordering points in a queue makes the algorithm try hardest for the first point: its shortest-path portal edge and recursive queue placement create a highway preserving the original root-to-point distance.The construction’s surprising consequence is an O(log log i) · radx0(X) bound for later points, despite the loss from each star partition.Source: §2 · p. 4
  • The central-ball queue interleaves ball points with regular and fat-cone portals, gaining either in the cone path or in the ball path to offset the star partition’s 1 + ǫ radial-distance loss.Regular-cone portals are ordered by the earliest queue point in their cones; fat-cone portals support a gain in the ball part, while the ball queue orders points in X0.Source: §2 · pp. 4–5, §2.1 · p. 7

2.1 Bounding the radius stretch

  • The hierarchical-star-partition algorithm achieves O(log log n) radius stretch, with dT(x0, z1) = dX(x0, z1), dT(x0, zi) ≤ i · radx0(X) for 1 < i < 216, and dT(x0, zi) = O(log log i) · radx0(X) otherwise.The point-specific bounds are stated for any queue ordering of X\{x0}; the section summarizes the overall radius stretch as O(log log n).Source: §2 · p. 3, §2.1 · pp. 5, 7
  • The cited passage states s ≤ (3/2)i^(2/3), equivalently i ≥ (2/3)s^(3/2), without specifying here what s counts or how the inequality is derived.Source: §2.1 · p. 10
  • The hierarchical-star-partition algorithm yields a single spanning tree with stretch bounded by O(log n · (log log n)^3).It uses ImpConeDecompose with parameters based on rad(X) and log log n.Source: §2.1 · p. 10
  • The construction uses ImpConeDecompose from, choosing the first portal on a shortest path to the first queued point in its first iteration.The cone-cutting method has average stretch roughly O(log n · log log n · 1/ε); with ε = 1/log log n and tree radius growth O(log log n), this yields the corollary.Source: §2.1 · p. 10

3 Strong Diameter Probabilistic Partitions

The section bounds edge-separation probability in a changing graph using random star partitions, then sums those bounds across scales to control expected stretch. Its analysis uses cone radii chosen by uniform or truncated-exponential sampling and obtains an O(log n · (log log n)^2 · log log log n) edge-stretch bound.

3 Strong Diameter Probabilistic Partitions

  • O(log log n) · radx(i) 0 (X(i)) bounds the tree distance from a cluster center to a point in the cluster.Source: §3 · p. 11
  • O(log n · (log log n)^2 · log log log n) · d(u, v) bounds the expected stretch numerator for any edge (u, v).The bound follows from a telescopic sum over scales.Source: §3 · p. 11
  • The cut-probability analysis handles a graph that changes after each cluster is removed, and its proof uses the truncated-exponential approach of.Source: §3 · p. 11
  • Cone centers are selected on shortest paths, while central-ball and first-cone radii are sampled uniformly and later cone radii use a truncated exponential distribution.The later cone choice uses a parameter determined by the preceding cuts.Source: §3 · pp. 11–12

A Extending to Weighted Graphs

Two adjustments extend the algorithm to weighted graphs: adding imaginary points during cone cuts and contracting sufficiently short edges during recursion. The contraction argument uses slack in the radius bound to ensure that expanding the contracted edges preserves it.

A Extending to Weighted Graphs

  • An imaginary point y′j placed on edge yj, xj at distance radx0(X0) from x0 restores the cone-cut inequality used in the algorithm.The change adds at most one imaginary point per original edge.Source: A Extending to Weighted Graphs · p. 16
  • Contracting edges shorter than c∆/n ensures each edge is at risk in at most O(log n) recursive steps, while proof slack preserves the radius bound after expansion.The argument requires c < c′, where c′∆ is the available slack.Source: A Extending to Weighted Graphs · p. 16

B Improving the stretch slightly

The appendix replaces a constant radius-growth factor with a slowly increasing iterated-log function to improve the asymptotic stretch bound. The resulting bound is O(log n · (log log n)^2 · log log log n) times the edge length.

B Improving the stretch slightly

  • A slowly increasing iterated-log function replaces the arbitrary c log log i radius-growth bound to optimize asymptotic stretch.The passage defines log(t) n and ϕt(n) for the analysis.Source: B Improving the stretch slightly · p. 17
  • The refined induction bounds dT(x0, zi) by i · radx0(X) for 1 < i < c and by c · log(t) i · radx0(X) otherwise.Source: B Improving the stretch slightly · p. 17
  • O(log n · (log log n)^2 · log log log n) · d(u, v) is the resulting bound on expected stretch for an edge.The proof substitutes c = 218 log(t) n, t = (log∗n)/2, and the stated parameter bounds.Source: B Improving the stretch slightly · p. 19

C Proof of some claims

The appendix proves auxiliary inequalities for iterated logarithms by induction. These estimates support the refined radius analysis.

C Proof of some claims

Loading 0808.2017v1…