Steiner shortcuts in graphs require large diameters with few edges

Polynomial Lower Bounds for Steiner Shortcuts via Test Functions

Data Structures and Algorithms

Summary

The paper studies a question about simplifying complex networks while keeping their essential connections. It asks whether adding new points and connections can make the network much easier to navigate without losing any paths between original points. The authors show that even when adding extra points (called Steiner vertices), it's still impossible to make the network much simpler without making some paths very long. They developed a new mathematical method called test functions to prove this, which might be useful in other problems too.

What this means in practice

  • For parallel algorithm designers: Avoid assuming efficient network shortcuts with Steiner vertices for fast sublinear-depth parallel graph algorithms.
  • For network protocol developers: Recognize limitations in optimizing reachability shortcuts when adding intermediate nodes in directed networks under constrained edge counts.

A theory result. No direct application yet.

Authors

Aaron Bernstein, Henry Fleischmann, Bernhard Haeupler, Gary Hoppenworth, Thatchaphol Saranurak

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.