New Techniques and Improved Approximation Algorithms for Connectivity Augmentation Problems

• Applicant: Dr. Felix Hommelsheim
• Subject Area: Theoretical Computer Science
• Term: since 2026
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 573939419

Designing robust and fault-tolerant networks is a fundamental task in communication, transportation, and energy systems. In practice, it is often sufficient to ensure that the network remains connected even after the failure of a single link, since multiple simultaneous failures are rare and a first failure can typically be repaired before another occurs. This naturally leads to the study of 2-edge-connectivity, a particularly relevant level of redundancy that offers a practical compromise between reliability and cost. From a theoretical perspective, the corresponding 2-edge-connected spanning subgraph problem (2ECSS) and its weighted variants lie at the core of approximation algorithm research, yet remain only partially understood due to their combinatorial complexity and APX-hardness. This project focuses on developing improved approximation algorithms for key special cases of weighted 2ECSS, in particular the unweighted 2ECSS and the Forest Augmentation Problem. These problems are of both practical and theoretical interest and have seen significant recent progress. A central motivation for this proposal is our recent result—a 5⁄4-approximation for unweighted 2ECSS, accepted at STOC 2025—which introduces new structural and combinatorial techniques that advance the current state of the art. The project builds on these ideas and aims to extend them to the Forest Augmentation Problem and closely related variants. Additional challenges include gaining a deeper understanding of the problem's inherent hardness and improving known inapproximability bounds. This proposal follows up on a previously submitted DFG project, which addressed similar problems using a computer-aided proof approach. Although that proposal was not funded—mainly due to insufficient detail on how correctness and implementation of the proof would be ensured—the research it initiated led directly to the STOC result. In the course of that work, we developed new, fully analytical techniques that replaced the need for computer verification. The present proposal reflects this shift and also broadens the scope, addressing both earlier criticisms and promising new directions.

• DFG Programme: Research Grants