Source-linked AI summary
Improved Lower Bound for Steiner Point Removal
Karthekeyan Chandrasekaran, Chandra Chekuri, Qingyun Chen, Weihao Zhu
TL;DR
Steiner Point Removal asks for a terminal-only minor that preserves terminal distances with low stretch. This work adapts Chen and Tan’s low-degree high-girth construction and analyzes it using expansion, improving the unconditional lower bound to Ω(√log k).
Problem
Steiner Point Removal asks for a T-minor minimizing stretch between terminals in an edge-weighted graph.
Source: §1 · p. 2Method
The paper uses low-degree high-girth expanders in a construction like Chen and Tan’s, then exploits expansion and girth in a modular lower-bound analysis.
Source: §1 · p. 2Results
The unconditional lower bound on achievable stretch is Ω(√log k).
Source: §1 · p. 2Takeaways & Limitations
The lower bound does not rely on any computational intractability assumption.
Source: §1 · p. 2The analysis is tight for the constructed instances, so improving the lower bound may require a substantially different construction.
Source: §1 · p. 2
Abstract
from arXiv · showhide
In the Steiner Point Removal problem, we are given a graph $G=(V,E)$ with an edge-length function $\ell_G: E\rightarrow \mathbb{R}_+$ and a subset $T\subseteq V$ of terminals. The goal is to find a minor $H=(T, E_H)$ of $G$ on vertex set $T$ such that the shortest path metric derived from $G$ on the edges of $H$ preserves the distance between every pair of terminals within a small multiplicative stretch. Filtser proved that a stretch of $O(\log |T|)$ can be achieved (in polynomial time), while Chen and Tan more recently proved a lower bound of $\Omega\left(\sqrt{\frac{\log |T|}{\log\log |T|}}\right)$ on the achievable stretch. Their lower bound is via a simple construction involving low-degree high-girth graphs. The existence of such graphs is guaranteed through the existence of low-degree high-girth expanders. In this work, we improve the lower bound to $\Omega(\sqrt{\log |T|})$ using the same simple construction of Chen and Tan but with a more careful analysis that exploits the expansion property.
1 Introduction
Steiner Point Removal seeks a terminal-only graph minor with low stretch; this work improves the unconditional lower bound on achievable stretch to Ω(√log k). It uses a low-degree high-girth expander construction and an analysis that exploits expansion.
1 Introduction
- SPR seeks a T-minor on the terminals that minimizes stretch, while retaining the graph’s minor structure.The input is an edge-weighted graph with k terminals; non-terminals are Steiner points.Source: §1 · p. 2
- The lower bound improves to Ω(√log k), unconditionally and without computational intractability assumptions.The prior lower bound was Ω(√(log |T|/log log |T|)).Source: §1 · p. 2
- The construction follows Chen and Tan, using low-degree high-girth expanders and pendant terminals with edge length Θ(√log k).The earlier construction used pendant-edge length Θ(√log k log log k); the original graph vertices are Steiner points.Source: §1 · p. 2
- The proof uses expansion to show that low stretch forces a short path with many crossings between contraction clusters, while large girth then contradicts small stretch.The contradiction follows because the terminal path must either have a long image in the original graph or use many minor edges.Source: §1 · p. 2
- The analysis is tight for the constructed instances, so improving the lower bound may require a substantially different construction.The paper frames this as a boundary on what its current construction can establish.Source: §1 · p. 2
2 Preliminaries
The preliminaries define terminal-minor stretch and establish that it cannot shorten terminal distances. They also set notation for paths, lengths, and graph structure.
2 Preliminaries
- Every T-minor with induced edge lengths has terminal distances at least as large as those in the original graph.Each minor edge receives the original-graph distance between its terminal endpoints.Source: §2 · p. 3
- Path length is the sum of its edge lengths, and girth is the length of the shortest cycle.The preliminaries also define d-regular graphs and the edge boundary δ(S).Source: §2 · p. 3
3 The Instance
The instance is built from a low-degree, high-girth expander and one pendant terminal for each of its vertices. Original graph edges have length 1, while terminal edges have length L = ⌈√log k⌉.
3 The Instance
- G0 is chosen as a low-degree, high-girth expander, with edge expansion and girth properties guaranteed for arbitrarily large k.The stated properties include |δ(S)| ≥ |S|/20 for |S| ≤ k/2 and girth at least log k/10.Source: §3 · p. 3
- The construction adds one terminal t_u adjacent to each vertex u of G0, assigns original edges length 1 and terminal edges length L = ⌈√log k⌉.The resulting graph has 2k vertices, and the k pendant vertices form the terminal set.Source: §3 · p. 3
- Figure 1 depicts the construction for k = 4, with the four G0 vertices on one side and their corresponding terminals on the other.G0 edges have length 1; all other edges have length L.Source: Figure 1 · p. 4
4 Properties of the instance
The instance’s structure constrains how a low-stretch terminal minor can contract vertices and represent edges. Expansion then guarantees a path with many special edges, a key property used to establish large stretch.
4 Properties of the instance
- A T-minor can be represented by mapping each nonterminal vertex to its contracted terminal; the vertices mapped to one terminal induce a connected subgraph of G0.Nonterminal vertices cannot be deleted in this construction, since deleting one would isolate its pendant terminal.Source: §4 · p. 4
- Every edge of a T-minor has length at least L.This lower bound applies to each edge in the terminal minor, not just to a particular chosen path.Source: §4 · p. 4
- For distinct vertices u and v in G0, a u-v path P and walk Q either satisfy P ⊆ Q or have combined length at least the girth.This property is used to compare a candidate path in G0 with walks representing terminal paths in the minor.Source: §4 · p. 4
- For stretch α ≤ 200, the path from a terminal to a vertex contracted to it is unique, and each minor edge’s shortest representing path contains exactly one special edge.A special edge has endpoints mapped to different terminals.Source: §4 · pp. 5–6
- The expansion property guarantees many special edges crossing each contracted set B_u, since |δ(B_u)| ≥ |B_u| when |B_u| ≤ k/2.These boundary edges are special because their endpoints lie on opposite sides of B_u.Source: §4 · pp. 6–7
- If every contracted vertex set B_u has size at most k/2, some L-edge path in G0 contains at least L/60 special edges.The proof counts L-edge paths and the appearances of special edges, then applies the pigeonhole principle.Source: §4 · pp. 6, 8
5 Proof of Large Stretch
The proof studies how a low-stretch minor can contract vertices into terminals, then uses the instance’s expansion and girth properties to force large stretch. Its analysis exploits expansion beyond the earlier Chen and Tan analysis.
5 Proof of Large Stretch
- Assuming stretch α ≤ 200, the proof first rules out any contracted set B_u larger than k/2 using the bound on how far vertices can be contracted.A vertex in an oversized set would lie farther than log k/50 from its terminal, contradicting Lemma 3.Source: §5 · p. 8
- With every |B_u| ≤ k/2, the proof selects an L-edge path containing at least L/60 special edges and compares it with a walk induced by a shortest terminal path in the minor.The comparison splits into whether the selected path is contained in that walk or not.Source: §5 · pp. 8–9
- The proof obtains a √log k-scale stretch lower bound for sufficiently large k.The concluding estimate is stated for sufficiently large k.Source: §5 · p. 9
- The analysis strengthens Chen and Tan’s nearly identical construction by exploiting G0’s expansion property, which their analysis did not use.Expansion is used in the argument guaranteeing a path with many special edges.Source: §5 · p. 9
6 Tightness of the instance
The instance’s Ω(√log k) lower bound is tight: a T-minor exists with ℓG-stretch O(√log k). The proof contracts each base vertex with its corresponding terminal, preserving adjacency between terminals according to the base graph.
6 Tightness of the instance
- A T-minor of the constructed graph has ℓG-stretch O(√log k), matching the instance’s lower-bound order.The section identifies this upper bound as showing the Ω(√log k) bound is tight for the instance.Source: §6 · pp. 9–10
- Contracting each base vertex u with its terminal t_u yields a T-minor where terminals are adjacent exactly when their base vertices are adjacent.Every edge in this minor has length 2L + 1.Source: §6 · p. 9
- A shortest base-graph path of length r lifts to a shortest terminal path in the minor of length (2L + 1) · r.The lifted path follows the terminals corresponding to the vertices on the base path.Source: §6 · p. 9