Steiner Point Removal --- Distant Terminals Don't (Really) Bother

Yun Kuen Cheung

Abstract

Given a weighted graph $G=(V,E,w)$ with a set of $k$ terminals $T\subset V$, the Steiner Point Removal problem seeks for a minor of the graph with vertex set $T$, such that the distance between every pair of terminals is preserved within a small multiplicative distortion. Kamma, Krauthgamer and Nguyen (SODA 2014, SICOMP 2015) used a ball-growing algorithm to show that the distortion is at most $\mathcal{O}(\log^5 k)$ for general graphs. In this paper, we improve the distortion bound to $\mathcal{O}(\log^2 k)$. The improvement is achieved based on a known algorithm that constructs terminal-distance exact-preservation minor with $\mathcal{O}(k^4)$ (which is independent of $|V|$) vertices, and also two tail bounds on the sum of independent exponential random variables, which allow us to show that it is unlikely for a non-terminal being contracted to a distant terminal.

Introduction

In the analysis of large-scale networks, it is often desirable to simplify a complex graph while preserving the essential distances between a specific subset of nodes, known as terminals. This is the core of the Steiner Point Removal (SPR) problem. Given a weighted graph $G$ and a set of $k$ terminals $T$, the goal is to construct a new graph $G'$ consisting only of the terminals $T$ such that $G'$ is a minor of $G$.

The "minor" constraint is significant: it means $G'$ must be obtainable from $G$ through vertex deletions, edge deletions, and edge contractions. This requirement ensures that $G'$ inherits structural properties from $G$; for instance, if $G$ is planar, $G'$ must also be planar. The quality of this simplification is measured by distortion ($\kappa$), the factor by which the shortest-path distances between terminals in $G'$ increase relative to their original distances in $G$.

The Challenge of Distortion

Previous research by Kamma, Krauthgamer, and Nguyen (KKN) established that for any general graph, the SPR problem can be solved with a distortion of $O(\log^5 k)$. However, a significant gap remained between this upper bound and the known lower bound of 8. This paper bridges that gap significantly, improving the upper bound to $O(\log^2 k)$.

Methodology: A Two-Stage Approach

The improvement stems from a combination of a structural preprocessing step and a refined probabilistic analysis of the "ball-growing" technique.

1. Preprocessing via the KNZ Step

A major hurdle in analyzing SPR is that the number of non-terminal (Steiner) points can be arbitrarily large compared to the number of terminals $k$. To address this, the author utilizes a technique by Krauthgamer et al. (KNZ) to reduce the input graph to a minor containing only $O(k^4)$ vertices while preserving terminal distances exactly. This preprocessing step makes the subsequent analysis independent of the original vertex set size $|V|$, allowing the focus to remain solely on the number of terminals $k$.

2. Randomized Ball-Growing

The core algorithm is a variation of the KKN "ball-growing" method. In this process, each terminal $t \in T$ "grows" a region (a ball) around itself. The radius of each ball is determined by an independent Exponential Random Variable (ERV). Every non-terminal node in the graph is then assigned to the terminal whose ball reaches it first. The final minor is formed by contracting these non-terminal nodes into their assigned terminals.

3. New Probabilistic Tail Bounds

The primary theoretical contribution lies in the analysis of these ERVs. The author derives two new tail bounds for the sum of independent exponential random variables. These mathematical tools allow for a much tighter proof that "bad events"—specifically, a Steiner node being assigned to a terminal that is geographically distant—are extremely unlikely.

Key Insights: Why Distant Terminals Don't Bother

The paper’s title, "Distant Terminals Don't (Really) Bother," highlights the central intuition. In earlier analyses, the potential for a node to be "captured" by a very distant terminal created significant distortion. By leveraging the memoryless property of exponential distributions and the new tail bounds, this work proves that the probability of such an assignment decays rapidly.

Furthermore, by shrinking the graph to $poly(k)$ size first, the author defines a finite, manageable set of "bad events." If the randomized algorithm avoids these $poly(k)$ events, the distortion is guaranteed to stay low. Unlike the KKN approach, which required separate treatments for low-diameter and high-diameter graphs, this analysis is direct and universal, leading to a more elegant proof.

Results and Implications

The paper successfully proves that for any weighted graph, the SPR problem can be solved with $O(\log^2 k)$ distortion with high probability ($1 - O(1/k)$).

While the asymptotic improvement is the main result, the author also provides a concrete upper bound: for a sufficiently large $k$, the distortion is at most $(2 \times 10^8) \cdot \log^2 k$. Although the constant factor is large, it represents a transition from purely asymptotic existence to a rigorous, calculable bound.

Future Work

Despite the improvement to $O(\log^2 k)$, a gap still exists between this result and the lower bound of 8. The author suggests that the current constant factor is loose and could be optimized. More fundamentally, reaching a constant distortion bound may require moving beyond standard probabilistic concentration tools like Chernoff bounds, which lose their effectiveness when the memoryless property of ERVs is not perfectly maintained. The author points toward modern queueing theory as a potential source for more advanced tools to further refine ball-growing strategies.

Summary updated

Abstract

Given a weighted graph $G=(V,E,w)$ with a set of $k$ terminals $T\subset V$, the Steiner Point Removal problem seeks for a minor of the graph with vertex set $T$, such that the distance between every pair of terminals is preserved within a small multiplicative distortion. Kamma, Krauthgamer and Nguyen (SODA 2014, SICOMP 2015) used a ball-growing algorithm to show that the distortion is at most $\mathcal{O}(\log^5 k)$ for general graphs. In this paper, we improve the distortion bound to $\mathcal{O}(\log^2 k)$. The improvement is achieved based on a known algorithm that constructs terminal-distance exact-preservation minor with $\mathcal{O}(k^4)$ (which is independent of $|V|$) vertices, and also two tail bounds on the sum of independent exponential random variables, which allow us to show that it is unlikely for a non-terminal being contracted to a distant terminal.
BibTeX
@inproceedings{cheung2018steiner,
  author = {Yun Kuen Cheung},
  title = {{Steiner Point Removal --- Distant Terminals Don't (Really) Bother}},
  booktitle = {SODA},
  year = {2018},
  doi = {10.1137/1.9781611975031.89},
}

Loading related content...

Figure