Chandra Chekuri

activity

20242026

collaborators

Showing 2026Show all

4 papers · 1 filter

cs.DS2026

Improved Lower Bound for Steiner Point Removal

Karthekeyan Chandrasekaran, Chandra Chekuri, Qingyun Chen +1

In the Steiner Point Removal problem, we are given a graph $G = (V, E)$ with an edge-length function $ℓ_{G} : E \to R_{+}$ and a subset $T \subseteq V$ of terminals. The…

cs.DS2026

A Polymatroidal Perspective on Random Contraction

Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu

Karger's elegant random contraction algorithm for finding a global mincut in a graph has been highly influential. More recent work has obtained several different (nonuniform) rando…

cs.DS2026

An iterative rounding $2$ -approximation for Feedback Vertex Set via AI-assisted proof of an extreme point property

Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni

We consider the Feedback Vertex Set problem (FVS): the input is an undirected graph $G = (V, E)$ and the goal is to find a minimum-cardinality (or a min-cost in the weighted case) sub…

cs.DS2026

Multiobjective Hypergraph Min-Cut in Quasi-Polynomial Time

Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu

We study the multiobjective hypergraph min-cut problem: Given a hypergraph $H = (V, E)$ and $k$ cost functions $c_{1}, c_{2}, \dots, c_{k} : E \to Z_{\geq 0}$ , the goal is to find a no…

Improved Lower Bound for Steiner Point Removal

A Polymatroidal Perspective on Random Contraction

An iterative rounding 2-approximation for Feedback Vertex Set via AI-assisted proof of an extreme point property

Multiobjective Hypergraph Min-Cut in Quasi-Polynomial Time

An iterative rounding $2$ -approximation for Feedback Vertex Set via AI-assisted proof of an extreme point property