CS Paper Radar

Sublinear Approximations for Spanning Tree Congestion

Sunny Atalig, Marek Chrobak, Petr Kolman, Hans Raj Tiwary

cs.DS ·submitted 2026-11-04 09:24 UTC · v1
theory

Abstract

The spanning tree congestion of a connected graph \(G\) is the minimum, over all spanning trees \(T\) of \(G\), of the maximum number of edges of \(G\) crossing a cut induced by deleting an edge of \(T\). In the spanning tree congestion problem we are asked to compute a spanning tree with minimum congestion. We describe two sublinear-ratio approximation algorithms for the spanning tree congestion problem (STC): a simple $\Ot(n^{8/9})$-approximation, and a more involved $\Ot(n^{2/3})$-approximation, where the notation $\Ot$ hides factors polynomial in $\log n$.. Until now, no algorithm with sublinear ratio was known. We also prove that for any fixed $0<\varepsilon<1$, approximation of the spanning tree congestion within $2-\varepsilon$ is NP-hard. This improves the previous best known lower bound $6/5$.

Closest papers

Nearest neighbours by meaning across the whole index.

Flows in High Degree Places: Sublinear Spanning Tree Congestion

cs.DS ·2026-11-09 ·D Ellis Hershkowitz, Richard Z Huang
similarity 0.85
Abstract

The congestion of a spanning tree $T$ of graph $G$ is the maximum congestion of an edge of $T$ if each edge of $G$ is routed on $T$. Prior work showed that obtaining a minimum congestion spanning tree is NP-hard to approximate within $6/5$, yet the only known approximation algorithm is a trivial $n/2$-approximation from returning any spanning tree of the graph. We give a simple poly-time $\tilde{O}(n^{6/7})$-approximation for minimum congestion spanning tree on $n$-vertex graphs. We obtain this result via a $\tilde{O}(m^{2/3})$-approximation, where $m$ is the number of edges. Our algorithm is based on a new \textit{flow-or-degree decomposition} which deletes a small number of edges so that each remaining component either has low degree or admits a low congestion flow. We also show that, assuming the Small Set Expansion Hypothesis, it is NP-hard to $O(1)$-approximate this problem, even on graphs of constant maximum degree.

0.04

A Sublinear Approximation Algorithm for Minimum Dilation Trees in the Plane

cs.CG ·2026-09-08 ·Sarita de Berg, Jacobus Conradi, Peter Kramer, André Nusser, Sampson Wong
similarity 0.70
Abstract · 46 pages, 18 figures

The dilation of a geometric graph measures how much longer the path between pairs of points becomes when restricted to graph edges, rather than following the direct path through the ambient space. The minimum dilation tree of a point set is the spanning tree with minimum dilation, where edge lengths in the tree are given by distances in the ambient space. In the Euclidean plane, computing the minimum dilation tree is NP-hard, but no hardness of approximation result is known. On the other hand, the minimum spanning tree is an $(n-1)$-approximation to the minimum dilation tree, but no asymptotically-better approximation algorithm is known for general point sets in the Euclidean plane. We give the first sublinear approximation algorithm for the minimum dilation tree in the Euclidean plane. Our approximation ratio is $\tilde{O}(n^{14/15})$ and our algorithm runs in polynomial time. This resolves an open problem proposed by Eppstein in 1996.

0.33

Logarithmic Embeddings into Probabilistic Spanning Trees for Distances and Capacities

cs.DS ·2026-11-03 ·Mohammad Hajiaghayi
theory similarity 0.66
Abstract

We prove that every connected $n$-vertex graph admits a probabilistic embedding into its spanning trees with expected distance stretch $O(\log n)$. This settles the logarithmic stretch conjecture of Alon, Karp, Peleg, and West, whose spanning-tree game appeared at the 1991 DIMACS Workshop on On-Line Algorithms and in SIAM Journal on Computing in 1995. A weighted form of the theorem also yields a distribution over spanning trees with capacities exactly equal to their fundamental graph cuts. Every tree dominates every graph cut, every cut is approximated within $O(\log n)$ in expectation, and the same capacity distribution defines an $O(\log n)$-competitive fractional oblivious routing. The distance and capacity distributions may differ. Diamond graphs give matching logarithmic lower bounds for stretch, congestion, and cut distortion. For rational input, both distributions are constructed deterministically in polynomial time and use at most $m$ trees, where $m$ is the number of graph edges. We prove an $Ω(m/ρ)$ support lower bound for congestion $ρ$; in particular, $(1-o(1))m$ trees can be necessary for near-unit congestion, even when the optimum tends to one. Thus linear dependence on $m$ is unavoidable in this regime. The weighted theorem combines a protected-geodesic petal decomposition with a pathwise entropy bound for locally selected centers. A local averaging inequality derandomizes the radii, and an adaptive rational packing procedure constructs the distributions.

0.54

Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction

cs.DS cs.DC ·2026-09-05 ·Peter Robinson, Ming Ming Tan
theory similarity 0.66
Abstract

We present the first polynomial lower bounds for several fundamental problems in the distributed graph sketching model in the tiny-error regime, which includes deterministic algorithms as a special case. In the graph sketching model, every node sends a single message to the referee who does not have any prior knowledge of the graph and must output the answer. While the work of Nelson and Yu (SODA 2019) and Yu (SODA 2021) showed that $Θ( \log^3n )$ is optimal for constructing a spanning forest or deciding whether the graph is connected with error at most $\frac{1}{\text{poly}(n)}$ , their approach does not yield any stronger bounds for significantly smaller error probabilities. Our main result is to show that solving either connectivity or spanning tree construction with error at most $δ$ requires messages of length $Ω( \min\{n, \log_2 \frac{1}δ\}^{1/3} )$, which implies that algorithms with exponentially small error must send messages of $Ω( n^{1/3} )$ bits in the worst case. Our results significantly narrows the current gap between the Jelani-Yu threshold of $Θ( \log^3n )$ and the trivial upper bound of sending $O(n)$ bits per node for deterministic graph sketching. We also extend our results to $k$-edge connectivity. For any $k=O(n^{1/7})$, we recover the same bound of $Ω( k )$ on the message length for algorithms with exponentially small error that was shown by Robinson and Tan (PODS 2026) only for deterministic algorithms. Finally, for $k=n^{o(1)}$, our result implies a stronger lower bound of $Ω_ε( n^ε )$ bits, for any constant $ε<\tfrac{1}{3}$.

0.09

Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update Time

cs.DS ·2026-09-30 ·Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh
top venue similarity 0.65
Abstract · To appear in FOCS 2026

We give fully dynamic algorithms for maintaining connectivity, minimum spanning tree, and $2$-edge connectivity of a graph with worst-case polylogarithmic update time. Our algorithms are randomized and succeed with high probability against an adaptive adversary. For the minimum spanning tree and $2$-edge connectivity problems, this improves over the subpolynomial update time bounds obtained by Nanongkai, Saranurak, and Wulff-Nilsen [FOCS'17], Jin and Sun [FOCS'21], and Jin, Sun, and Thorup [SODA'24], respectively. The only randomized component of our algorithms is the computation of static expander decompositions, and a deterministic algorithm for said problem would directly imply deterministic algorithms for all three problems. This reduction is novel even for the connectivity problem.

0.24

Metric TSP in Sublinear Time: Breaking Two Approximation

cs.DS ·2026-11-03 ·Amir Azarmehr, Soheil Behnezhad
similarity 0.65
Abstract

The seminal result of Czumaj and Sohler [STOC'04] showed that a 2-approximation of the value of metric TSP can be obtained with sublinear queries. Whether sublinear algorithms can break the 2-approximation barrier has remained a major open problem. See problem 71 on sublinear.info. This paper resolves this open problem. We show there are fixed $\varepsilon, δ> 0$ such that a $(2-δ)$-approximation of metric TSP value can be obtained with $O(n^{2-\varepsilon})$ queries. Here $n$ is the number of vertices, and the input size is $Θ(n^2)$.

0.23

Dynamic Steiner Tree under Edge Updates

cs.DS ·2026-11-03 ·Jeff Giliberti, MohammadTaghi Hajiaghayi, Mohammad Mahdavi, Xinchen Yang
hot direction similarity 0.65
Abstract

The Steiner tree problem is the canonical generalization of minimum spanning tree (MST). When connectivity is required only among a fixed subset of vertices (terminals), the goal is to maintain a minimum-cost tree connecting these terminals as the graph undergoes edge updates. While dynamic MST has been studied since the 1980s~[Frederickson, STOC'83, SICOMP'85], and the first sublinear-in-$n$ dynamic MST algorithm dates back almost thirty-five years to Eppstein, Galil, Italiano, and Nissenzweig~[FOCS'92, JACM'97], achieving sublinear-in-$n$ update time for dynamic Steiner tree has long remained open, as a single edge update can invalidate many routes in the underlying terminal metric closure. We present the first fully dynamic algorithm for Steiner tree that achieves a constant-factor approximation with sublinear-in-$n$ update time. For any fixed $0<ζ<1/2$, our deterministic algorithm maintains an $O_ζ(1)$-approximate Steiner tree for undirected graphs with polynomially bounded edge weights in $\widetilde O(n^{1/2+ζ})$ amortized update time, answering cost queries in $O(1)$ time, and reporting an explicit tree in $\widetilde O(n^{1+ζ})$ time. Our approach combines periodic terminal-metric rebuilds on a dynamic spanner with a top-tree dynamic program that localizes edge deletions and reconnects surviving components through a dynamic distance sparsifier. Along the way, we give a simpler randomized insertion-only algorithm with a better, explicit approximation ratio.

0.25

Tight Bounds for Sublinear Metric Steiner Tree

cs.DS ·2026-11-09 ·Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian
theory similarity 0.65
Abstract

In the metric Steiner tree problem we are given an $n$-point metric space $(V,w)$ and a set $T\subseteq V$ of terminals, and we seek the smallest weight $\mathrm{OPT}$ of a tree that spans $T$ and may use points of $V\setminus T$. We study sublinear algorithms in the distance-oracle model, where the algorithm knows $V$ and $T$ upfront and can query the distance function $w$. The objective is to estimate $\mathrm{OPT}$ while querying significantly fewer than $n^2$ distances. The minimum spanning tree on $T$ estimates $\mathrm{OPT}$ within a factor $2$, and its weight can be approximated with $\widetilde{O}(n)$ queries. The natural question that has been studied is therefore the query complexity of estimating $\mathrm{OPT}$ within a factor strictly below $2$. Chen, Khanna, and Tan [SODA 2023] gave such an algorithm using $\widetilde{O}(n^{13/7})$ queries, and a lower bound of $\widetildeΩ(n^{6/5})$. Later Mahabadi, Roghani, Tarnawski, and Vakilian [ITCS 2025] improved the algorithm to $\widetilde{O}(n^{5/3})$, and Mahabadi, Tarnawski, and Vakilian [ITCS 2027] improved the lower bound to $\widetildeΩ(n^{7/5})$. In this work we settle the above question. We give an algorithm that estimates $\mathrm{OPT}$ within a factor $2-η_0$, for an absolute constant $η_0>0$, with query (and time) complexity $\widetilde{O}(n^{3/2})$. We also show that the exponent $3/2$ is tight.

0.12