arXiv preprint ·
Polynomial Lower Bounds for Steiner Shortcuts via Test Functions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The Steiner shortcut problem asks whether every directed graph $G=(V,E)$ with $n$ vertices and $m$ edges admits an augmentation $G_{+}=(V\cup V_{+},E\cup E_{+})$ with $m^{1+o(1)}$ edges such that $G_+$ has the same reachability structure as $G$ (i.e. for all $s,t\in V$, $s$ reaches $t$ in $G$ iff $s$ reaches $t$ in $G_+$), and the diameter of $G_{+}$ is $m^{o(1)}$. This is a core combinatorial question underlying many reachability algorithms in the dynamic, streaming, and CONGEST models, and all parallel algorithms with almost-linear work and sublinear depth. A sequence of works ruled out such a shortcut $G_{+}$ in the non-Steiner setting where $V_{+}=\emptyset$. However, as recently shown by Bernstein et al. [STOC '26], all known non-Steiner lower-bound constructions fail once Steiner vertices $V_{+}$ are allowed. This paper rules out almost-optimal Steiner shortcuts: we show an infinite family of graphs $G=(V,E)$ with the property that, for any $\varepsilon>0$, a Steiner shortcut $G_{+}=(V\cup V_{+},E\cup E_{+})$ with $m^{1+\varepsilon}$ edges must have diameter at least $n^{1/56-O(\varepsilon)}$. Our construction strengthens the standard non-Steiner lower-bound framework via an additional structure that allows Steiner vertices to be replaced by original vertices; we can then reduce back to the standard arguments without Steiner vertices. This new structure is achieved via a new general strategy based on test functions, which is quite flexible and can potentially be extended to applications beyond our work. We also generalize our lower bound to exact Steiner hopsets in undirected graphs and to depth reduction for monotone circuits. The latter significantly strengthens the classical lower bound based on Sylvester matrices.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics
Quadratic-Time Barriers from Self-Referential SAT
Sublinear Metric Distortion for Matching
Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
Near linear mixing of random-cluster Glauber dynamics on random regular graphs
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.