Skip to content
Preprint

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

Sep 2026 · 0 citations · 11 references
Computer Science

TL;DR

A new structural analysis of the Bamas--Drygala--Svensson LP-guided DFS algorithm is given, which 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.

Abstract

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.

View source

Similar papers

Preprint Aug 2026

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

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

Morteza Alimi · 0 citations
#edge computing Preprint Oct 2026

Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation

This paper analyzes a matching problem in which the cost of each edge is a vector with $k$ components and provides various results including FPT-membership for parameters $k$ and $Z$ combined, as well as W[P]-membership and W[SAT]-hardness for each of the two parameters individually.

Jonas Friemel, Tilo Hoitz, Phillip Keldenich et al. · 0 citations
Preprint Sep 2026

An iterative rounding $2$-approximation for Feedback Vertex Set via AI-assisted proof of an extreme point property

We consider the Feedback Vertex Set problem (FVS): the input is an undirected graph $G=(V,E)$ and the goal is to find a minimum-cardinality (or a min-cost in the weighted case) subset $S \subseteq V$ of vertices such that $G-S$ has no cycles. A $2$-approximation via the local-ratio method was developed in the mid 90's...

K. Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni · 0 citations
Preprint Oct 2026

Faster high-accuracy multicommodity flow in dense graphs

We give a fast algorithm for solving min-cost $k$-commodity flow. The basic idea is to construct an auxiliary linear program that has low rank and whose minimum value is at most $1/k$ times the minimum value of the original problem (thus, solving this auxiliary linear program will make at least $1/k$ fraction of progre...

Chen-Xin Dai, Alicia Stepin, Colin Tang · 0 citations
Preprint Aug 2026

Exact SAT Solving for the Two-Dimensional Bandwidth Minimization Problem

The results demonstrate that the proposed SAT approach provides an effective exact method for the small- and medium-sized benchmark instances considered in this study, with fewer than 400 vertices, while heuristic methods remain important for larger and more challenging instances.

Minh Quang Pham, Dao Xuan Nghia, T. Van-Khanh · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.