2026-09-10T09:44:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27724 2026-09-09T12:19:35Z ddc:004 open_access

Improved Approximation Algorithms for Bounded-Length Path Augmentation Hommelsheim, Felix Approximation algorithms path augmentation connectivity augmentation survivable network design 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Felix Hommelsheim 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.7 urn:nbn:de:0030-drops-277247 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.7 eng https://creativecommons.org/licenses/by/4.0/legalcode