CS Paper Radar

Approximation Algorithms for Maximum-Weight Degree-Bounded Forests

Theophile Thiery, Vera Traub, Nicola Widmer

cs.DS math.CO ·submitted 2026-11-01 13:11 UTC · v1
publishedtheory

Abstract

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.

Comment
to appear in SOSA 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Computing Forest Degree Realizations with Minimum Cardinality Domination

cs.DS cs.DM ·2026-11-04 ·Amotz Bar-Noy, Omri Kosary, David Peleg, Dror Rawitz
similarity 0.68
Abstract

In the Degree Realization problem with respect to a family $\mathcal{P}$ of graphs the input is a non-increasing sequence $d = (d_1,\ldots,d_n)$ of positive integers, and the goal is to decide whether there exists a simple undirected graph $G \in \mathcal{P}$, whose degrees correspond to $d$, i.e., such that $deg(G) = d$. In this paper we consider the version of Degree Realization in which the realization is required to be a forest (i.e., $\mathcal{P}$ is the family of forests). We consider \emph{optimized} Degree Realization in which the goal is to obtain a realization that minimizes an objective function $f$. That is, the goal is to find a realization $G$ that minimizes $f(G)$ among the realizations of the given input sequence. More specifically, we focus on the following functions: the size of an optimal \emph{vertex cover} and the size of an optimal \emph{dominating set}. We also consider the \emph{total} and \emph{paired} versions of both Min Vertex Cover and Min Dominating Set. We provide characterizations and linear time realization algorithms for all the above-mentioned problems. Since Min Paired Vertex Cover is closely related to Min Edge Dominating Set, our results for Degree Realization with respect to the former extend to the latter.

0.21

Sharp lower bounds for weighted bisections of graphs with bounded maximum degree

cs.DM math.CO ·2026-11-17 ·Stefanie Gerke, Gregory Gutin, Anders Yeo, Yacong Zhou
theory similarity 0.68
Abstract

A bisection of a graph is a partition of its vertex set into two parts the sizes of which differ by at most one. We prove that every finite simple graph of maximum degree at most an odd positive integer $k$, with arbitrary nonnegative real edge weights, has a bisection of weight at least $(k+1)/(2k)$ times its total edge weight. The corresponding bound $(k+2)/(2(k+1))$ for even $k$ follows immediately. Both coefficients are best possible. Somewhat surprisingly, these are exactly the sharp coefficients known for maximum weighted cuts, despite the additional balance requirement.

0.19

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

Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs

cs.DS ·2026-10-19 ·Rares-Darius Buhai, Suprovat Ghoshal, Neng Huang, Pravesh Kothari, Euiwoong Lee +2 more
theory similarity 0.65
Abstract · 70 Pages

We give a polynomial-time algorithm that achieves an $α_{GW} + \tildeΩ(1/d)$-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most $d$ constraints. This improves on the $α_{GW}+\tildeΩ(1/d^2)$-approximation guarantee of [Hsieh-Kothari, ICALP'23]. We also show a matching Unique Games hardness under randomized polynomial-time reductions, thereby proving that the gain on $α_{GW}$ is optimal up to $\mathrm{polylog}(d)$ factors. Here, $α_{GW} \approx 0.878$ is the approximation ratio of the Goemans-Williamson algorithm. Our results resolve an open question due to Raghavendra and refute his conjectured optimal approximation ratio of $α_{GW} + \tildeΩ(1/\sqrt{d})$. Our local improvement scheme can be thought of as using an adaptive (based on the neighbors) shift applied to the Gaussian before using the GW sign rounding. This allows us to implement a ``soft but simultaneous'' flipping decision at each vertex as opposed to hard but sequential flipping decisions in prior works. Our hardness results are based on a new sparsification lemma for graphs produced by the reduction from Unique Games [Khot-Kindler-Mossel-O'Donnell, SICOMP'07] that preserves the optimal values up to a factor of $1 \pm ε$ while subsampling to an average degree of only $\tilde{O}(1/ε)$. This is the first example of a CSP in which the optimal advantage on degree-$d$ instances is asymptotically smaller than $O(1/\sqrt{d})$ [Trevisan, STOC'01]. A key idea in the proof of our sparsification theorem establishes new bounds on the number of ``nearly optimal'' cuts in the output of the KKMO reduction. This step, in turn, relies on a new, robust inverse Majority-Is-Stablest theorem.

0.15

A general algebraic characterization of extremal $Δ$-trees and $k$-cyclic graphs for degree-homogeneous VDB indices

cs.DM math.CO ·2026-10-25 ·Milan Bašić
similarity 0.64
Abstract · 16 pages, 1 figure

We present a general algebraic method for maximizing a vertex-degree-based (VDB) topological index $TI(G) = \sum_{uv \in E(G)} f(d(u),d(v))$ over the class of $n$-vertex trees with a prescribed maximum degree $Δ\ge 3$. By expressing the edge multiplicities of the basis $\mathcal{B} = \{(1,Δ), (Δ,Δ)\}$ via degree-sum identities, we reduce the maximization of $TI(T)$ to the minimization of an explicit discrete penalty function $G(x,y)$ over the non-basic edges. We formulate five analytical conditions on the weight function $f(x,y)$ that dictate the optimal edge distributions, yielding a complete characterization of the extremal trees across all congruence classes of $n \pmod{Δ- 1}$. Additionally, we provide their explicit construction by attaching leaves to a core of internal vertices. Applying this framework, we obtain the complete characterization of extremal $Δ$-trees for the Degree-Ratio Sombor ($DRSO$), Symmetric Division Deg ($SDD$), and Hyperbolic Sombor ($HSO$) indices for all $Δ\ge 3$. Furthermore, the analytical conditions identify the exact degree thresholds for the Arithmetic-Geometric ($AG$) and Diminished Sombor ($DSO$) indices, showing that the same extremal family maximizes $AG$ if and only if $3 \le Δ\le 8$, and $DSO$ if and only if $3 \le Δ\le 4$. Finally, since changing the edge count from $m = n - 1$ to $m = n - 1 + k$ affects only the constant term in the decomposition while leaving the penalty function $G(x,y)$ invariant, the method extends directly to connected $k$-cyclic graphs.

0.18

Two $(2+ε)$-Approximation Algorithms for Minimum Spanning Tree Interdiction

cs.DS ·2026-11-18 ·Junjie Luo, Changjun Wang, Chenhao Wang, Wei Yu
similarity 0.64
Abstract

Minimum spanning tree interdiction asks for edge deletions within a budget that maximize the weight of a remaining minimum spanning tree. We give two deterministic $(2+ε)$-approximation algorithms for every fixed $ε>0$, improving the previous best factor of $4$. Both algorithms respect the original budget and run in $N^{O(1/ε)}$ time for $0<ε\le1$, where $N$ is the binary input size. The first algorithm uses two weight thresholds to choose initial deletions that force every remaining spanning tree to contain edges at or above these thresholds. It then uses the remaining budget to further increase the MST weight through Lagrangian rounding. The second algorithm achieves the same guarantee through a different decomposition: it enumerates vertex partitions and heavy trees connecting their parts, then approximates a bounded-weight interdiction problem within the parts. An objective-preserving reduction from Maximum Components shows that, assuming the Small Set Expansion Hypothesis and $\mathsf P\ne\mathsf{NP}$, no deterministic polynomial-time $(2-δ)$-approximation exists for any fixed $0<δ<1$, even on simple graphs with weights in $\{0,1\}$. Thus, our approximation guarantee is conditionally tight up to an arbitrarily small additive constant. Finally, the MST guarantee yields a $(4+ε)$-approximation for metric-TSP interdiction.

0.15

Matroid Parity Meets Vertex Splitting

cs.DS cs.DM ·2026-11-14 ·Hitendra Kumar, Pritesh Kumar, Madhumita Kundu, Saket Saurabh
similarity 0.64
Abstract · 48 pages

A vertex split replaces a vertex by two non-adjacent descendants and partitions its incident edges between them. We study exclusive $\ell$-shallow splitting, where each original vertex has at most $\ell+1$ descendants, with the aim of obtaining a forest, a pseudoforest, or a cluster graph. We consider two natural objectives: minimizing the total number of split operations and minimizing the number of original vertices that are split. Our main conceptual contribution is a connection between vertex splitting and matroid parity. For both forests and pseudoforests, we give a characterization of feasible splitting sequences that leads, via weighted linear matroid parity, to polynomial-time algorithms for minimizing the number of split vertices when $\ell=2$. These algorithms are complemented by NP-hardness for every fixed $\ell\ge3$; for pseudoforests, hardness holds even on graphs of maximum degree four. The total number of split operations behaves differently: for both sparse target classes, this objective is polynomial-time solvable for every $\ell$, using matroid intersection. For cluster graphs, both objectives admit linear-time algorithms when $\ell=1$ and are NP-hard for every fixed $\ell\ge2$. Together, these results identify how the target class, the local splitting bound, and the choice of objective determine the complexity of vertex splitting.

0.33

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

cs.DS math.CO ·2026-09-24 ·Sogol Jahanbekam
theory similarity 0.63
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.

0.22