Tata Institute of Fundamental Research

Almost Tight Additive Guarantees for k-Edge-Connectivity

STCS Seminar
Speaker: Nikhil Kumar (TIFR)
Organiser: Raghuvansh Saxena
Date: Wednesday, 26 Nov 2025, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract: 

We study the k-edge-connected spanning subgraph (k-ECSS) problem: given an undirected graph G with nonnegative edge costs, the objective is to find a minimum-cost k-edge-connected spanning subgraph. For even k, we present a polynomial-time algorithm that constructs a k-edge-connected subgraph whose cost is at most the optimal value of the natural LP relaxation for k-ECSS. Since k-ECSS is NP-hard for all k ≥ 2, these guarantees are nearly optimal. Moreover, our results substantially improve upon the recent work of Hershkowitz, Klein, and Zenklusen, both in approximation quality and the simplicity of the algorithm and its analysis.