6 papers
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 applicat…
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…