CS Paper Radar

Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7

Sogol Jahanbekam

cs.DS math.CO ·submitted 2026-09-24 17:38 UTC · v1
theory

Abstract

We give a polynomial-time algorithm that constructs, in every connected $n$-vertex graph of minimum degree at least $7$, a spanning tree with at least $\frac{25200}{46189}n>0.5455\,n$ leaves. No bound specific to minimum degree $7$ was known: the best bound available for this class was $\frac{11}{21}n\approx0.5238\,n$, inherited from Simarova's theorem for minimum degree~$6$. The algorithm and its analysis are carried out for an arbitrary minimum degree $δ$, and yield a recursion that gives an explicit lower bound on the number of leaves for every $δ$. The resulting bounds improve all previously known ones for every $δ\ge7$; for $δ=8,9,10$ they are $0.5850\,n$, $0.6151\,n$ and $0.6413\,n$, and they are tabulated for $δ\le25$ at the end of the paper.

Closest papers

Nearest neighbours by meaning across the whole index.

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.64
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

Approximation Algorithms for Maximum-Weight Degree-Bounded Forests

cs.DS math.CO ·2026-11-01 ·Theophile Thiery, Vera Traub, Nicola Widmer
publishedtheory similarity 0.63
Abstract · to appear in SOSA 2027

In the maximum-weight degree-bounded forest problem, we are given a graph with nonnegative edge weights and a degree upper bound on each vertex. The objective is to find a maximum-weight forest satisfying the degree bounds. We show that this problem admits a simple $2$-approximation via the greedy algorithm. This already improves over the best-known guarantees obtained via a reduction to weighted $3$-matroid parity, and sets a baseline to improve upon. Our main result is an $\frac{8}{5}$-approximation algorithm for the maximum-weight degree-bounded forest problem. For the special case of uniform degree bounds, our algorithm achieves an approximation ratio of $\frac{3}{2}$. It computes two sets of edges, each of which we then restrict to a feasible solution in an optimal way, and finally returns the better of the two resulting solutions. To obtain the initial two edge sets, we first relax the degree bounds and leverage an algorithm by Lau and Singh [JACM'15] for degree-bounded spanning trees, and second we relax the forest constraints and employ an algorithm for maximum-weight $b$-matchings.

0.39

Sublinear Approximations for Spanning Tree Congestion

cs.DS ·2026-11-04 ·Sunny Atalig, Marek Chrobak, Petr Kolman, Hans Raj Tiwary
theory similarity 0.61
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$.

0.50

Not All Degree Constraints Are Created Equal when Computing Spanning Trees

cs.DS ·2026-08-26 ·Narek Bojikian, Alexander Firbas, Robert Ganian, Hung P. Hoang, Krisztina Szilagyi
publishedtheory similarity 0.60
Abstract · To appear at IPEC 2026. This is the original submitted version - reviewer comments will be incorporated in a later version

We study the computation of minimum spanning trees subject to local degree constraints. Recent work (ICALP 2026) established that three natural formalizations of this problem share the exact same parameterized complexity under standard structural graph parameters, including treewidth, pathwidth and clique-width. This applies to the cases where every vertex has a single target degree (Specified Degree MST), or a degree upper bound (Bounded Degree MST), or is equipped with a set of admissible degrees (Set of Degrees MST). In this paper, we investigate these problems under more restrictive parameterizations and reveal that their complexity landscapes fundamentally diverge on bounded-treedepth graphs. Specifically, we prove that the former two problems are fixed-parameter tractable when parameterized by the treedepth of the input graph. In sharp contrast, we show that Set of Degrees MST remains W[1]-hard parameterized by treedepth, even when combined with the feedback vertex number (i.e., deletion distance to treewidth $1$). Finally, we show that this divergence seems to be specific to treedepth: we exclude an analogous W[1]-hardness result for Set of Degrees MST w.r.t. the vertex cover number and also rule out fixed-parameter algorithms for the former two problems w.r.t. deletion distance to constant pathwidth.

0.19

Metric Dimension is NP-complete on Graphs of Treewidth Two

cs.CC cs.DM ·2026-10-15 ·Tristan Benoit
similarity 0.60
Abstract · v3: NP-completeness extended to two-connected two-terminal series-parallel graphs of pathwidth at most five; v2: open questions corrected. 8…

The metric dimension of a connected graph is the least number of vertices whose distance vectors distinguish all vertices. We show that deciding whether the metric dimension of a graph is at most a given integer is NP-complete on graphs of treewidth at most two, and even on two-connected two-terminal series-parallel graphs of pathwidth at most five. As the problem is polynomial on trees, the graphs of treewidth one, this settles the treewidth threshold of its hardness, which was known to lie between two and twenty-four. The reduction is from satisfiability of formulas in which every literal occurs at most twice. To such a formula with $n$ clauses and $r$ variables it associates a two-terminal series-parallel graph $G_\varphi$ with $O((n+r)^2)$ vertices and pathwidth at most five, whose metric dimension is $2(n+r)+7$ if the formula is satisfiable and $2(n+r)+8$ otherwise.

0.53

Beating Quadratic Time--Message Trade-off in Distributed Minimum Spanning Tree Construction

cs.DS cs.DC ·2026-08-31 ·Taisuke Izumi, Naoki Kitamura, Toshimitsu Masuzawa
similarity 0.60
Abstract

We present a new distributed algorithm for computing a minimum spanning tree (MST) in the \textsf{CONGEST-KT$_{1}$} model, where messages are limited to $O(\log n)$ bits and each vertex initially knows the identifiers of its neighbors. Our algorithm exposes a two-parameter time--message trade-off: for any $0 \leq λ\leq κ\leq 1/2$, it runs in $\tilde{O}(n^λD_G + n^{1 - κ- λ} + n^{1 - 2κ+ λ} + n^{1/2})$ rounds and uses $\tilde{O}(\min\{m, n^{1 + κ}\})$ messages, where $n$, $m$, and $D_G$ are the number of vertices, edges, and thenetwork diameter, respectively. In particular, setting $(κ, λ) = (1/3, 1/6)$ yields an MST algorithm running in $\tilde{O}(n^{1/2} + n^{1/6}D_G)$ rounds with only $\tilde{O}(n^{4/3})$ messages. Under the mild assumption $D_G = O(n^{1/3})$, this is round-optimal while improving the best known message bound of $\tilde{O}(n^{3/2})$. More broadly, our algorithm breaks the quadratic time--message trade-off barrier $\mathrm{\# rounds} \cdot \mathrm{\# messages} = \tildeΩ(n^2)$, which no previous MST algorithm in the \textsf{CONGEST-KT$_{1}$} model has been able to overcome, and it does so for almost the entire range of the diameter $D_G$. As a byproduct, we also obtain new low-message broadcast, spanning-tree, and leader-election algorithms.

0.18

A Low-Diameter Nash-Williams--Tutte Theorem

cs.DM math.COcs.DS ·2026-11-03 ·Pin-Hsian Lee, Peng-Ting Lin, Meng-Tsung Tsai, Ting-An Wu
theory similarity 0.60
Abstract

The Nash-Williams--Tutte theorem characterizes the existence of $k$ edge-disjoint spanning trees by a condition on every vertex partition. We prove that, for simple graphs, the same condition guarantees $k$ edge-disjoint spanning trees, each of diameter $O(n/δ)$ and with $O((n/δ)\log(δ+1))$ internal vertices, where $n$ is the number of vertices and $δ$ is the minimum degree. Both bounds hold simultaneously for every tree, with absolute implicit constants independent of $k$, and each is asymptotically optimal in general. Our proof is constructive and yields a randomized algorithm with expected running time $\tilde{O}(n^5)$. We derive applications to short edge-disjoint routes and weak linkages, small Steiner trees, and survivable networks with short paths. The joint bounds also yield low-diameter spanning Eulerian subgraphs and short tours for postman and general routing problems.

0.29

Flows in High Degree Places: Sublinear Spanning Tree Congestion

cs.DS ·2026-11-09 ·D Ellis Hershkowitz, Richard Z Huang
similarity 0.60
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