Nikhil Kumar

collaborators

Showing cs.DSShow all

4 papers · 1 filter

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_…

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.DS2024

Optimal Padded Decomposition For Bounded Treewidth Graphs

Arnold Filtser, Tobias Friedrich, Davis Issac +4

A $(β, δ, Δ)$ -padded decomposition of an edge-weighted graph $G = (V, E, w)$ is a stochastic decomposition into clusters of diameter at most $Δ$ such that for every vertex $v \in V$ , th…

cs.DS2024

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs

Syamantak Das, Nikhil Kumar, Daniel Vaz

Flow sparsification is a classic graph compression technique which, given a capacitated graph $G$ on $k$ terminals, aims to construct another capacitated graph $H$ , called a flow s…

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

Almost Tight Additive Guarantees for k-Edge-Connectivity

Optimal Padded Decomposition For Bounded Treewidth Graphs

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs

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