10 papers
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 with an edge-length function and a subset of terminals. The…
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…
An iterative rounding -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 and the goal is to find a minimum-cardinality (or a min-cost in the weighted case) sub…
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 and cost functions , the goal is to find a no…
Hedgegraph Polymatroids
Karthekeyan Chandrasekaran, Chandra Chekuri, Weihang Wang +1
Graphs and hypergraphs combine expressive modeling power with algorithmic efficiency for a wide range of applications. Hedgegraphs generalize hypergraphs further by grouping hypere…
Hypergraph Splitting-Off via Element-Connectivity Preserving Reductions
Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni
Bérczi, Chandrasekaran, Király, and Kulkarni (ICALP 2024) recently described a splitting-off procedure in hypergraphs that preserves local-connectivity and outlined some applicatio…
Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
Elfarouk Harb, Yousef Yassin, Chandra Chekuri
We study the problem of minimizing or maximizing the average value of a submodular or supermodular set function over non-empty subsets $ S \s…
Online Disjoint Spanning Trees and Polymatroid Bases
Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
Finding the maximum number of disjoint spanning trees in a given graph is a well-studied problem with several applications and connections. The Tutte-Nash-Williams theorem provides…
On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni
We consider deletion problems in graphs and supermodular functions where the goal is to reduce density. In Graph Density Deletion (GraphDD), we are given a graph with non…
On Sparsest Cut and Conductance in Directed Polymatroidal Networks
Chandra Chekuri, Anand Louis
We consider algorithms and spectral bounds for sparsest cut and conductance in directed polymatrodal networks. This is motivated by recent work on submodular hypergraphs \cite{Yosh…