CS Paper Radar

An 8/5 Rounding for Half-Integral Forest-BCR via Root Supports and Circuit Rank

Morteza Alimi

cs.DS ·submitted 2026-08-22 02:42 UTC · v1
theory

Abstract

We study the rounding of a supplied half-integral feasible solution of the root-assignment bidirected cut relaxation for Steiner Forest (Forest-BCR). Byrka, Grandoni, and Traub [IPCO 2025] proved a $16/9$ guarantee for a recursive framework that normalizes the LP point, selects a vertex set of maximum projected LP density, buys a minimum spanning tree on that set, contracts it, and recurses. We prove that the same framework has guarantee $8/5$. The new analysis keeps the orientation and the root label of each projected half-unit of LP mass. In a simple projection, the cut constraints at a terminal of degree two determine the root-assignment vector of every demand incident with it, and half-integrality leaves only two possibilities: a unit assignment to one root, which forces excess outdegree inside that root's support, or a split assignment to two roots, which forces overlap between their supports. For every connected component $C$ of the split-root graph this yields $ β_C\ \ge\ \frac{L_C}{2}$, where $β_C$ is the circuit rank of the union of the root supports in $C$ and $L_C$ is the number of its vertices of degree two in the full projection. Balancing the density certificate obtained from this inequality against the ordinary degree sum gives a vertex set of density at least $5/8$, and the inherited contraction lemma turns that into the $8/5$ rounding. For every $q\ge3$ we also construct a normalized half-integral point whose maximum projected density is exactly $5q/[2(4q-1)]$, so the universal projected-density bound is asymptotically tight.

Closest papers

Nearest neighbours by meaning across the whole index.

A Framework for Cost-Preserving Rounding with Applications to Laminar Thin Trees

cs.DS ·2026-11-13 ·Jannis Blauth, Rico Zenklusen
similarity 0.65
Abstract

In the context of finding thin trees, like laminarly-thin trees or globally-thin trees, it turned out to be challenging to round a fractional solution to an integral one without losing cost, while only having a constant-factor violation of the thinness constraints. We provide a general framework for this problem, in a much broader context, that reduces the problem to finding a certain type of rounding algorithm with only an approximate prize guarantee. We show that, up to a change in constants, the rounding problem with approximate prize guarantee that we use is equivalent to the original question. As an application, we obtain a polynomial-time algorithm that finds a laminar constantly-thin tree of cost no higher than the one of the natural linear programming solution, thus obtaining the first result without cost loss of this type (even for the special case of chain-constrained trees). Moreover, our framework gives a new perspective on how to approach the problem of finding globally-thin trees without cost loss.

0.32

A $59/33$ Cut-LP Guarantee for Matching Augmentation

cs.DS ·2026-09-22 ·Morteza Alimi, Tobias Mömke
theory similarity 0.62
Abstract · 20 pages, 6 figures

The Matching Augmentation Problem (MAP) asks for a minimum-cardinality set of unit-cost edges that, together with a zero-cost matching, forms a 2-edge-connected spanning multigraph. We study the standard cut relaxation. Bamas, Drygala, and Svensson proposed a particularly simple LP-guided algorithm: compute an extreme optimum, run a depth-first search that prioritizes large LP coordinates, and augment the resulting DFS tree optimally. We give a new structural analysis of the Bamas--Drygala--Svensson LP-guided DFS algorithm. The analysis combines an exact primal--dual identity for the residual uplink problem with a rank bound that measures fractional support relative to the unit-valued skeleton. The result is that for every root and every deterministic tie-breaking order consistent with the LP priorities, the algorithm returns a solution of cost at most $\frac{59}{33}c(x^*)-\frac{25}{33}=\left(2-\frac7{33}\right)c(x^*)-\frac{25}{33}\approx1.788c(x^*)-0.758$, where $x^*$ is an optimum of the cut LP. Consequently, the integrality gap of the relaxation is at most $59/33\approx1.788$. No new algorithmic step is required; the improvement is analytical. The exact packing certificate for the residual uplink problem yields a cost identity with a packing-slack term, while a rank theorem bounds fractional support relative to the unit-valued skeleton. A regional classification accounts for the non-tree edges, and a two-cut identity handles self-holes. As a direct corollary, the same $59/33\approx1.788$ bound holds for Forest Augmentation in the minimum-value regime. The proof is self-contained apart from one theorem on the dimension of minimum-cut vectors.

0.33

Approximation Algorithms for Maximum-Weight Degree-Bounded Forests

cs.DS math.CO ·2026-11-01 ·Theophile Thiery, Vera Traub, Nicola Widmer
publishedtheory similarity 0.60
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

Greedy Region Growing: Improved Approximations for Cutwidth, Pathwidth, Flow-Expander Decomposition, and More

cs.DS ·2026-10-12 ·Aditya Anand
theory similarity 0.60
Abstract · 46 pages, 5 figures. Corrected cross-reference labels caused by a TeX Live compatibility issue; mathematical content unchanged

We give a new rounding technique for spreading-metric linear programs, called Greedy Region Growing, which adapts the classical technique of region growing to min-max graph layout problems and flow-expander decomposition. Using this technique, we obtain state-of-the-art approximation algorithms for several fundamental problems. (1) An $O(\log n)$-approximation for Cutwidth and Pathwidth, improving upon the previous bound of $O(\log n\exp(O(\sqrt{\log\log n})))$ due to Bansal, Katzelnick, and Schwartz (FOCS 2024). This matches the $Ω(\log n)$ integrality gap of the standard LP relaxations. (2) An $O(\log n)$-approximation for their directed analogues, Minimum Storage and Minimum Register Sufficiency on directed acyclic graphs, improving the previous bound of $O(\log^{3/2} n)$. (3) A $φ$-flow-expander decomposition that cuts at most an $O(φ\log n\log\log n)$ fraction of the edges. This improves the $O(φ\log n\exp(O(\sqrt{\log\log n})))$ bound of Bansal, Jambulapati, and Saranurak (ICALP 2026), and is within an $O(\log\log n)$ factor of the graph-theoretic lower bound. The vertex version of our algorithm also gives an $O(\log n)$-approximation for Treedepth. In particular, our results answer several open problems of Bansal, Katzelnick, and Schwartz (FOCS 2024). Technically, we also solve the conceptual question raised by their work: our technique shows how to adapt Seymour recursion to min-max objectives, and constructs $O(1)$-weak local partitions in spreading metrics.

0.29

Path-constrained Packing on Trees

cs.DS ·2026-11-16 ·Samuel Fiorini, Raoul Luqué, Philipp Pabst, Britta Peis
similarity 0.59
Abstract · 36 pages, 5 figures, 1 table, 2 algorithms

An instance of Budgeted Path-constrained Packing on Trees (BPPT) consists of a graph $G$ together with a spanning tree $T$, a weight $w_e \in \mathbb{Z}_{\ge 0}$ for each tree edge $e \in E(T)$ and a budget $b_f \in \mathbb{Z}_{\ge 1}$ for each non-tree edge $f \in E(G) \setminus E(T)$. The goal is to find a maximum weight packing of fundamental cuts respecting the budgets. Equivalently, an instance of BPPT is an integer program of the form $\max \{w^\intercal x : Ax \le b,\ x \in \{0,1\}^n\}$ where $A \in \{0,1\}^{m \times n}$ is a transposed edge-path-tree matrix, $w \in \mathbb{Z}^n_{\ge 0}$ and $b \in \mathbb{Z}^m_{\ge 1}$. We define the congestion $C$ of a BPPT instance as the maximum number of non-zeros in a column of $A$. The unit congestion $UC$ is defined similarly, except that rows with $b_i \ge 2$ are ignored. We also consider the minimum budget $β:= \min \{b_i : i = 1, \ldots, m\}$. In this paper, we begin the study of BPPT through the lens of the three parameters $C$, $UC$ and $β$, and relative to the standard LP relaxation $\max \{w^\intercal x : Ax \le b,\ x \in [0,1]^n\}$. BPPT generalizes the independent set problem in graphs of maximum degree at most $C$ and is a special case of the $b$-matching problem in hypergraphs of rank at most $C$. We obtain approximation algorithms for BPPT with factors $2+UC/2$, $1+C/2$ and $β/(β-1)$ for $β\geq 2$. These bounds are relative to the standard LP relaxation and, as we show, integrality gap tight with respect to parameters $UC$ and $β$, and almost integrality gap tight relative to $C$. We complement these results with a $\lceil (C+1)/3 \rceil$-approximation for fixed $C$ which is not relative to the standard LP relaxation and has $\textsf{XP}$ running time parameterized by $C$.

0.24

Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition

cs.DS ·2026-09-02 ·Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak, Haoze Wang
theory similarity 0.59
Abstract

We study the low-degree Steiner forest decomposition. Given a graph $G=(V,E)$ and a terminal set $U\subseteq V$, the standard decomposition returns a set $X\subseteq V$ of size at most $|U|/2$ and a forest $T\subseteq G-X$ of maximum degree $Δ$ such that, for every connected component $C$ of $G-X$, some connected component of $T$ contains all terminals in $U\cap V(C)$. This is the central decomposition behind several connectivity oracles under vertex failures [DP20, LS22, LW24]. The state-of-the-art algorithms either take $O(mn\log n)$ time with degree bound $4$ [DP20], or take $m^{1+o(1)}$ time with the weaker degree bound $O(\log^{2}n)$ [LW24]. We show that if $T$ is allowed to contain vertices of $X$, then a degree-$4$ decomposition can be computed by a very simple algorithm in $O(mα(n))$ time. Further, we show that this relaxed decomposition is equally useful for constructing connectivity oracles under vertex failures. As a consequence, we obtain a deterministic connectivity oracle under $d$ vertex failures with $\tilde{O}(m)$ space, $\tilde{O}(md_\star)$ preprocessing time ($d_\star$ is an upper bound on the number of failed vertices), $\tilde{O}(d^{2})$ update time, and $O(d)$ query time. Up to polylogarithmic factors, this oracle strictly improves all known oracles; in particular, it removes the $n^{o(1)}$ factors from the preprocessing and update times of [LS22, LW24].

0.24

Reversing the Mostar line-graph inequality with long pendant paths

cs.DM math.CO ·2026-09-30 ·Kerem Kat
theory similarity 0.58
Abstract · 19 pages, 4 figures. Ancillary code for exact finite checks

Let $K_t$ be obtained by attaching a pendant path of length $t$ to a fixed rooted graph $K$. We prove that $\mathrm{Mo}(L(K_t))-\mathrm{Mo}(K_t)$, the difference between its line-graph and original Mostar indices, is exactly affine on each parity class beyond a sharp uniform cutoff. The slope depends on distance-level neighbor counts and is positive for every non-bipartite core. Triangle chains give infinitely many graphs with $\mathrm{Mo}(L(G))>\mathrm{Mo}(G)$ at every positive cyclomatic number $c$, with maximum degree three, resolving Alex-Indulal Problem 3.3. At zero slope, a cactus branch-mass formula decides equality; identical vertex profiles need not give identical intercepts. Fixed cores giving equality for all sufficiently long attachments exist exactly when $c$ is odd. Maximum degree three suffices, and at every even $c$ a binary-tree construction gives equality on one eventual parity class.

0.20

On (Directed) Width-Parameters of Geometric Spanners

cs.CG ·2026-09-18 ·Kevin Buchin, Carolin Rehs, Torben Scheele
published similarity 0.57
Abstract · Accepted at ISAAC 2026

To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) $t$-spanner $G$ for a point set $P$ in the Euclidean space is a (directed) graph such that for every pair of points, the shortest path in $G$ is at most a factor $t$ longer than the Euclidean distance between those points. In this paper, we investigate $t$-spanners that are bounded by certain graph parameters. Let $κ$ be a graph parameter. We show that for path-width, branch-width and cut-width there is an $\mathcal{O}(n/k^{d/(d-1)})$-spanner $G$ on $P$ with $κ(G)=k$ and that this is asymptotically worst-case optimal. In $\mathbb{R}^2$ we show the same bounds for planar graphs of clique-width or rank-width $k$. In contrast, for tree-depth, we show that there are sets of points for which the dilation cannot be bounded. Therefore, we investigate computing a spanner with tree-depth $k$ and minimum dilation. We show that already for tree-depth $3$ this problem is NP-hard to approximate within any factor strictly less than $\sqrt{2}$, and present an XP-algorithm to compute for a given tree-depth $k$ a graph with dilation at most $2t^*$, where $t^*$ is the minimum dilation. We further extend these results to obtain directed $\mathcal{O}(n/k^{d/(d-1)})$-spanners $G$ with $κ(G)=k$ for $κ$ being directed tree-width, directed path-width or DAG-width and show that also in the directed case, this is asymptotically worst-case optimal.

0.29