Karthekeyan Chandrasekaran
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Karthekeyan Chandrasekaran has a total of 50 co-authors. Here are the top co-authors by number of shared publications:
- Kristóf Bérczi
MTA-ELTE Matroid Optimization Research Group and HUN-REN–ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd University, and HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary
6 shared publications - Tamás Király
MTA-ELTE Matroid Optimization Research Group and HUN-REN-ELTE Egerváry Research Group, Department of Operations Research, ELTE Eötvös Loránd University, Budapest, Hungary
6 shared publications - Weihang Wang
University of Illinois Urbana-Champaign, Champaign, USA
5 shared publications - Calvin Beideman
University of Illinois Urbana-Champaign, Urbana, Illinois 61801
4 shared publications - Chandra Chekuri
University of Illinois, Urbana-Champaign, Urbana, USA
4 shared publications - Shubhang Kulkarni
University of Illinois, Urbana-Champaign, Urbana, USA
4 shared publications
Latest Publications
- 7 October 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (4) , 1785-1813
Online Disjoint Spanning Trees and Polymatroid Bases
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 [A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003]. Several other packing problems such as element disjoint Steiner trees, disjoint set covers, and disjoint dominating sets are NP-Hard but admit an [Formula: see text]-approximation [U. Feige, M. M. Halldórsson, G. Kortsarz, and A. Srinivasan, SIAM J. Comput., 32 (2002), pp. 172–195], [J. Cheriyan and M. R. Salavatipour, ACM Trans. Algorithms, 3 (2007), 47]. Călinescu, Chekuri, and Vondrák [G. Călinescu, C. Chekuri, and J. Vondrák, Random Structures Algorithms, 35 (2009), pp. 418–430] 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 [A. Pananjady, V. K. Bagaria, and R. Vaze, The online disjoint set cover problem and its applications, in Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM), 2015, pp. 1221–1229], [Y. Emek, A. Goldbraikh, and E. Kantor, Online disjoint set cover without prior knowledge, in 27th Annual European Symposium on Algorithms (ESA), 2019, 44], [M. Bienkowski, J. Byrka, and Ł. Jeż, Online disjoint set covers: Randomization is not necessary, in 42nd International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, 2025, 18]. 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 [K. Quanrud, Quotient sparsification for submodular functions, in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2024, pp. 5209–5248]. We generalize the previously known result for the online disjoint set cover problem [Y. Emek, A. Goldbraikh, and E. Kantor, Online disjoint set cover without prior knowledge, in 27th Annual European Symposium on Algorithms (ESA), 2019, 44] 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 polylogarithmic competitive ratio.
- 7 October 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (4) , 1785-1813
Online Disjoint Spanning Trees and Polymatroid Bases
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 [A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003]. Several other packing problems such as element disjoint Steiner trees, disjoint set covers, and disjoint dominating sets are NP-Hard but admit an [Formula: see text]-approximation [U. Feige, M. M. Halldórsson, G. Kortsarz, and A. Srinivasan, SIAM J. Comput., 32 (2002), pp. 172–195], [J. Cheriyan and M. R. Salavatipour, ACM Trans. Algorithms, 3 (2007), 47]. Călinescu, Chekuri, and Vondrák [G. Călinescu, C. Chekuri, and J. Vondrák, Random Structures Algorithms, 35 (2009), pp. 418–430] 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 [A. Pananjady, V. K. Bagaria, and R. Vaze, The online disjoint set cover problem and its applications, in Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM), 2015, pp. 1221–1229], [Y. Emek, A. Goldbraikh, and E. Kantor, Online disjoint set cover without prior knowledge, in 27th Annual European Symposium on Algorithms (ESA), 2019, 44], [M. Bienkowski, J. Byrka, and Ł. Jeż, Online disjoint set covers: Randomization is not necessary, in 42nd International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, 2025, 18]. 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 [K. Quanrud, Quotient sparsification for submodular functions, in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2024, pp. 5209–5248]. We generalize the previously known result for the online disjoint set cover problem [Y. Emek, A. Goldbraikh, and E. Kantor, Online disjoint set cover without prior knowledge, in 27th Annual European Symposium on Algorithms (ESA), 2019, 44] 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 polylogarithmic competitive ratio.
- 22 July 2026
- Published by Springer Nature in Mathematical Programming
- p. 1-44
Hypergraph connectivity augmentation in strongly polynomial time
- 22 July 2026
- Published by Springer Nature in Mathematical Programming
- p. 1-44
Hypergraph connectivity augmentation in strongly polynomial time
- 13 June 2026
- Published by Springer Nature
- p. 331-345
Hedgegraph Polymatroids
- Open Access
- 13 March 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1073
Approximating submodular matroid-constrained partitioning
- 13 March 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1073
Open AccessApproximating submodular matroid-constrained partitioning
- Open Access
- 9 October 2025
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 176, 319-383
Splitting-off in hypergraphs
- 9 October 2025
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 176, 319-383
Open AccessSplitting-off in hypergraphs
- 4 June 2025
- Published by Springer Nature
- p. 72-85
Monotone Submodular Multiway Partition
- Open Access
Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
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.
Open AccessMinimum Cost Nowhere-zero Flows and Cut-balanced Orientations
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.
- 4 January 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 214 (1-2) , 153-200
Polyhedral aspects of feedback vertex set and pseudoforest deletion set
- 4 January 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 214 (1-2) , 153-200
Polyhedral aspects of feedback vertex set and pseudoforest deletion set
- 16 December 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (4) , 3198-3219
Approximating Submodular \({k}\)-Partition via Principal Partition SequenceIn submodular [Formula: see text]-partition, the input is a submodular function [Formula: see text] (given by an evaluation oracle) along with a positive integer [Formula: see text], and the goal is to find a partition of the ground set [Formula: see text] into [Formula: see text] nonempty parts [Formula: see text] in order to minimize [Formula: see text]. Narayanan, Roy, and Patkar [ J. Algorithms, 21 (1996), pp. 306–330] designed an algorithm for submodular [Formula: see text]-partition based on the principal partition sequence and showed that the approximation factor of their algorithm is 2 for the special case of graph cut functions (which was subsequently rediscovered by Ravi and Sinha [ European J. Oper. Res., 186 (2008), pp. 77–90]). In this work, we study the approximation factor of their algorithm for three subfamilies of submodular functions—namely monotone, symmetric, and posimodular—and show the following results: (1) The approximation factor of their algorithm for monotone submodular [Formula: see text]-partition is [Formula: see text]. This result improves on the 2-factor that was known to be achievable for monotone submodular [Formula: see text]-partition via other algorithms. Moreover, our upper bound of [Formula: see text] matches the recently shown lower bound under polynomial number of function evaluation queries [R. Santiago, Proceedings of the International Workshop on Combinatorial Algorithms, IWOCA, 2021, pp. 516–530]. Our upper bound of [Formula: see text] is also the first improvement beyond 2 for a certain graph partitioning problem that is a special case of monotone submodular [Formula: see text]-partition. (2) The approximation factor of their algorithm for symmetric submodular [Formula: see text]-partition is 2. This result generalizes their approximation factor analysis beyond graph cut functions. (3) The approximation factor of their algorithm for posimodular submodular [Formula: see text]-partition is 2. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is [Formula: see text].
- 16 December 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (4) , 3198-3219
Approximating Submodular \({k}\)-Partition via Principal Partition SequenceIn submodular [Formula: see text]-partition, the input is a submodular function [Formula: see text] (given by an evaluation oracle) along with a positive integer [Formula: see text], and the goal is to find a partition of the ground set [Formula: see text] into [Formula: see text] nonempty parts [Formula: see text] in order to minimize [Formula: see text]. Narayanan, Roy, and Patkar [ J. Algorithms, 21 (1996), pp. 306–330] designed an algorithm for submodular [Formula: see text]-partition based on the principal partition sequence and showed that the approximation factor of their algorithm is 2 for the special case of graph cut functions (which was subsequently rediscovered by Ravi and Sinha [ European J. Oper. Res., 186 (2008), pp. 77–90]). In this work, we study the approximation factor of their algorithm for three subfamilies of submodular functions—namely monotone, symmetric, and posimodular—and show the following results: (1) The approximation factor of their algorithm for monotone submodular [Formula: see text]-partition is [Formula: see text]. This result improves on the 2-factor that was known to be achievable for monotone submodular [Formula: see text]-partition via other algorithms. Moreover, our upper bound of [Formula: see text] matches the recently shown lower bound under polynomial number of function evaluation queries [R. Santiago, Proceedings of the International Workshop on Combinatorial Algorithms, IWOCA, 2021, pp. 516–530]. Our upper bound of [Formula: see text] is also the first improvement beyond 2 for a certain graph partitioning problem that is a special case of monotone submodular [Formula: see text]-partition. (2) The approximation factor of their algorithm for symmetric submodular [Formula: see text]-partition is 2. This result generalizes their approximation factor analysis beyond graph cut functions. (3) The approximation factor of their algorithm for posimodular submodular [Formula: see text]-partition is 2. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is [Formula: see text].
- Open Access
Scarf's Algorithm on Arborescence Hypergraphs
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.
Open AccessScarf's Algorithm on Arborescence Hypergraphs
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.