Nikhil Kumar

collaborators

3 papers

cs.DS2025

Almost Tight Additive Guarantees for $k$ -Edge-Connectivity

Nikhil Kumar, Chaitanya Swamy

We consider the \emph{ $k$ -edge connected spanning subgraph} (kECSS) problem, where we are given an undirected graph $G = (V, E)$ with nonnegative edge costs ${c_{e}}_{e \in E}$ , and…

cs.DS2025

Optimal Padded Decomposition For Bounded Treewidth Graphs

Arnold Filtser, Tobias Friedrich, Davis Issac +4

A $(I^^{2}, I^´, I^)$ -padded decomposition of an edge-weighted graph $G = (V, E, w)$ is a stochastic decomposition into clusters of diameter at most $I^$ such that for every vertex $v \in V$ …

cs.DS2025

Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique

Nikhil Kumar, JJ Nan, Chaitanya Swamy

In the classical \emph{survivable-network-design problem} (SNDP), we are given an undirected graph $G = (V, E)$ , non-negative edge costs, and some $(s_{i}, t_{i}, r_{i})$ tuples, where $s_…

Almost Tight Additive Guarantees for k-Edge-Connectivity

Optimal Padded Decomposition For Bounded Treewidth Graphs

Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique

Almost Tight Additive Guarantees for $k$ -Edge-Connectivity