8 papers
-Separating Principal Partition Sequence of Submodular Functions
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
Narayanan showed the existence of the principal partition sequence of a submodular function, a structure with numerous applications in areas such as clustering, fast algorithms, an…
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…
Monotone Submodular Multiway Partition
Richard Bi, Karthekeyan Chandrasekaran, Soham Joshi
In submodular multiway partition (SUB-MP), the input is a non-negative submodular function given by an evaluation oracle along with termi…
Approximating Submodular Matroid-Constrained Partitioning
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
The submodular partitioning problem asks to minimize, over all partitions of a ground set , the sum of a given submodular function over the parts of . The problem has…
Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
Karthekeyan Chandrasekaran, Siyue Liu, R. Ravi
Flows and colorings are disparate concepts in graph algorithms -- the former is tractable while the latter is intractable. Tutte introduced the concept of nowhere-zero flows to uni…