Improved Approximation Algorithms for Bounded-Length Path Augmentation
Felix Hommelsheim · arXiv (Cornell University) · 2025
The Forest Augmentation Problem (FAP) asks for a minimum set of additional edges (links) that makes a given forest 2-edge-connected while spanning all vertices. A key special case is the Path Augmentation Problem (PAP), where the input forest consists of vertex-disjoint paths. Grandoni, Jabal Ameli, and Traub [STOC'22] recently broke the long-standing 2-approximation barrier for FAP, achieving a 1.9973-approximation. A crucial component of this result was their 1.9913-approximation for PAP; the first better-than-2 approximation for PAP. In this work, we present a 1.9412-approximation for bounded-length PAP, in which each path of the input forest has constant length p_max. The running-time of our algorithm is O(n^p_max). One of our key innovations is a (11/6 + ε)-approximation preserving reduction to so-called structured instances, which simplifies the problem and enables our improved approximation. Additionally, we introduce a new relaxation inspired by 2-edge covers and analyze it via a corresponding packing problem, where the relationship between the two problems is similar to the relationship between 2-edge covers and 2-matchings. Using a factor-revealing LP, we bound the cost of our solution to the packing problem w.r.t. the relaxation and derive a strong initial solution. We then transform this solution into a feasible PAP solution, combining techniques from FAP and related connectivity augmentation problems, along with new insights.