About

Karthekeyan Chandrasekaran is an Associate Professor in the Industrial and Enterprise Systems Engineering department at the University of Illinois at Urbana-Champaign. He earned his Ph.D. in Algorithms, Combinatorics, and Optimization from Georgia Institute of Technology in 2012 and his Bachelor of Technology in Computer Science and Engineering from the Indian Institute of Technology, Madras, in 2007. His research interests include probabilistic methods and analysis, algorithms, mathematical programming, and combinatorial optimization, with a focus on theory and algorithms. Chandrasekaran has received notable awards such as the Best Ph.D. Thesis Award from Sigma Xi at Georgia Tech and the College of Computing Dissertation Prize. He has held visiting fellow positions at the Institute for Computational and Experimental Research in Mathematics (ICERM) and Eotvos Lorand University. Since joining the University of Illinois in 2014, he has contributed to teaching courses such as Deterministic Models in Optimization, Integer Programming, and Combinatorial Optimization.

Research topics

• Combinatorics
• Mathematics
• Discrete mathematics
• Mathematical optimization

Selected publications

• Approximating submodular matroid-constrained partitioning

  Theoretical Computer Science · 2026-03-13

  articleOpen accessSenior author

  The submodular partitioning problem asks to minimize, over all partitions P of a ground set V , the sum of a given submodular function f over the parts of P . The problem has seen considerable work in approximability, as it encompasses multiterminal cuts on graphs, k -cuts on hypergraphs, and elementary linear algebra problems such as matrix multiway partitioning. This research has been divided between the fixed terminal setting, where we are given a set of terminals that must be separated by P , and the global setting, where the only constraint is the size of the partition. We investigate a generalization that unifies these two settings: minimum submodular matroid-constrained partition. In this problem, we are additionally given a matroid over the ground set and seek to find a partition P in which there exists some basis that is separated by P . We explore the approximability of this problem and its variants for general, symmetric, and monotone submodular functions.

  PublisherDOI

• Splitting-off in hypergraphs

  Journal of Combinatorial Theory Series B · 2025-10-09

  articleOpen access
  PublisherDOI

• Polyhedral aspects of feedback vertex set and pseudoforest deletion set

  Mathematical Programming · 2025-01-04 · 1 citations

  article1st authorCorresponding
  PublisherDOI

• Online Disjoint Spanning Trees and Polymatroid Bases

  ArXiv.org · 2025-01-01

  preprintOpen access1st authorCorresponding

  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 a min-max relation for this problem which also extends to disjoint bases in a matroid and leads to efficient algorithms [Schrijver, 2003]. Several other packing problems such as element disjoint Steiner trees, disjoint set covers, and disjoint dominating sets are NP-Hard but admit an O(log n)-approximation [Feige et al., 2002; Cheriyan and Salavatipour, 2007]. Călinescu, Chekuri, and Vondrák [G. Călinescu et al., 2009] viewed all these packing problems as packing bases of a polymatroid and provided a unified perspective. Motivated by applications in wireless networks, recent works have studied the problem of packing set covers in the online model [Pananjady et al., 2015; Emek et al., 2019; Bienkowski et al., 2025]. The online model poses new challenges for packing problems. In particular, it is not clear how to pack a maximum number of disjoint spanning trees in a graph when edges arrive online. Motivated by these applications and theoretical considerations, we formulate an online model for packing bases of a polymatroid, and describe a randomized algorithm with a polylogarithmic competitive ratio. Our algorithm is based on interesting connections to the notion of quotients of a polymatroid that has recently seen applications in polymatroid sparsification [Quanrud, 2024]. We generalize the previously known result for the online disjoint set cover problem [Emek et al., 2019] and also address several other packing problems in a unified fashion. For the special case of packing disjoint spanning trees in a graph (or a hypergraph) whose edges arrive online, we provide an alternative to our general algorithm that is simpler and faster while achieving the same poly-logarithmic competitive ratio.

  PublisherOA PDFDOI

• Monotone Submodular Multiway Partition

  Lecture notes in computer science · 2025-01-01

  book-chapter
  PublisherDOI

• Approximating Submodular Matroid-Constrained Partitioning

  ArXiv.org · 2025-06-24

  preprintOpen access

  The submodular partitioning problem asks to minimize, over all partitions $P$ of a ground set $V$, the sum of a given submodular function $f$ over the parts of $P$. The problem has seen considerable work in approximability, as it encompasses multiterminal cuts on graphs, $k$-cuts on hypergraphs, and elementary linear algebra problems such as matrix multiway partitioning. This research has been divided between the fixed terminal setting, where we are given a set of terminals that must be separated by $P$, and the global setting, where the only constraint is the size of the partition. We investigate a generalization that unifies these two settings: minimum submodular matroid-constrained partition. In this problem, we are additionally given a matroid over the ground set and seek to find a partition $P$ in which there exists some basis that is separated by $P$. We explore the approximability of this problem and its variants, reaching the state of the art for the special case of symmetric submodular functions, and provide results for monotone and general submodular functions as well.

  PublisherOA PDFDOI

• Minimum Cost Nowhere-Zero Flows and Cut-Balanced Orientations

  ArXiv.org · 2025-01-01

  articleOpen access1st authorCorresponding

  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 unify these two concepts. Jaeger showed that nowhere-zero flows are equivalent to cut-balanced orientations. Motivated by connections between nowhere-zero flows, cut-balanced orientations, Nash-Williams' well-balanced orientations, and postman problems, we study optimization versions of nowhere-zero flows and cut-balanced orientations. Given a bidirected graph with asymmetric costs on two orientations of each edge, we study the min cost nowhere-zero $k$-flow problem and min cost $k$-cut-balanced orientation problem. We show that both problems are NP-hard to approximate within any finite factor. Given the strong inapproximability result, we design bicriteria approximations for both problems: we obtain a $(6,6)$-approximation to the min cost nowhere-zero $k$-flow and a $(k,6)$-approximation to the min cost $k$-cut-balanced orientation. For the case of symmetric costs (where the costs of both orientations are the same for every edge), we show that the nowhere-zero $k$-flow problem remains NP-hard and admits a $3$-approximation.

  PublisherOA PDFDOI

• On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions

  ArXiv.org · 2025-01-01

  articleOpen access1st authorCorresponding

  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 $G=(V,E)$ with non-negative vertex costs and a non-negative parameter $ρ\ge 0$ and the goal is to remove a minimum cost subset $S$ of vertices such that the densest subgraph in $G-S$ has density at most $ρ$. This problem has an underlying matroidal structure and generalizes several classical problems such as vertex cover, feedback vertex set, and pseudoforest deletion set for appropriately chosen $ρ\le 1$ and all of these classical problems admit a $2$-approximation. In sharp contrast, we prove that for every fixed integer $ρ> 1$, GraphDD is hard to approximate to within a logarithmic factor via a reduction from Set Cover, thus showing a phase transition phenomenon. Next, we investigate a generalization of GraphDD to monotone supermodular functions, termed Supermodular Density Deletion (SupmodDD). In SupmodDD, we are given a monotone supermodular function $f:2^V \rightarrow \mathbb{Z}_{\ge 0}$ via an evaluation oracle with element costs and a non-negative integer $ρ\ge 0$ and the goal is remove a minimum cost subset $S \subseteq V$ such that the densest subset according to $f$ in $V-S$ has density at most $ρ$. We show that SupmodDD is approximation equivalent to the well-known Submodular Cover problem; this implies a tight logarithmic approximation and hardness for SupmodDD; it also implies a logarithmic approximation for GraphDD, thus matching our inapproximability bound. Motivated by these hardness results, we design bicriteria approximation algorithms for both GraphDD and SupmodDD.

  PublisherOA PDFDOI

• Approximating Submodular Matroid-Constrained Partitioning

  SSRN Electronic Journal · 2025-01-01

  preprintOpen access
  PublisherDOI

• Scarf's Algorithm on Arborescence Hypergraphs

  arXiv (Cornell University) · 2024-12-04

  preprintOpen access1st authorCorresponding

  Scarf's algorithm--a pivoting procedure that finds a dominating extreme point in a down-monotone polytope--can be used to show the existence of a fractional stable matching in hypergraphs. The problem of finding a fractional stable matching in a hypergraph, however, is PPAD-complete. In this work, we study the behavior of Scarf's algorithm on arborescence hypergraphs, the family of hypergraphs in which hyperedges correspond to the paths of an arborescence. For arborescence hypergraphs, we prove that Scarf's algorithm can be implemented to find an integral stable matching in polynomial time. En route to our result, we uncover novel structural properties of bases and pivots for the more general family of network hypergraphs. Our work provides the first proof of polynomial-time convergence of Scarf's algorithm on hypergraphic stable matching problems, giving hope to the possibility of polynomial-time convergence of Scarf's algorithm for other families of polytope.

  PublisherOA PDFDOI

Recent grants

• AF: Small: Cuts, Connectivity and Partitioning in Graphs, Hypergraphs and Beyond

  NSF · $500k · 2019–2024

• AF: Small: Collaborative Research: Matrix Signings and Algorithms for Expanders and Combinatorial Nullstellensatz

  NSF · $250k · 2018–2023

Frequent coauthors

• Elena Grigorescu

  Purdue University West Lafayette

  18 shared

• Santosh Vempala

  Georgia Institute of Technology

  17 shared

• Weihang Wang

  14 shared

• Tamás Király

  13 shared

• Kristóf Bérczi

  13 shared

• Venkata Gandikota

  13 shared

• Calvin Beideman

  University of Illinois Urbana-Champaign

  12 shared

• Vivek Madan

  Johns Hopkins University

  11 shared

Awards & honors

• Best Ph.D. Thesis Award, Sigma Xi Chapter, Georgia Institute…
• College of Computing Dissertation Prize, Georgia Institute o…