KCKarthekeyan Chandrasekaran

Karthekeyan Chandrasekaran

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Karthekeyan Chandrasekaran has a total of 50 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Online Disjoint Spanning Trees and Polymatroid Bases

    by 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 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.

  • Hypergraph connectivity augmentation in strongly polynomial time

    by Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Shubhang Kulkarni

  • Hedgegraph Polymatroids

    by Karthekeyan Chandrasekaran, Chandra Chekuri, Weihang Wang, Weihao Zhu

  • Open Access

    Approximating submodular matroid-constrained partitioning

    by Kristóf Bérczi, Tamás Király, Daniel P. Szabo, Karthekeyan Chandrasekaran


  • Open Access

    Splitting-off in hypergraphs

    by Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Shubhang Kulkarni

  • Monotone Submodular Multiway Partition

    by Richard Bi, Karthekeyan Chandrasekaran, Soham Joshi

  • Open Access

    Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations

    by 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 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.

  • Polyhedral aspects of feedback vertex set and pseudoforest deletion set

    by Karthekeyan Chandrasekaran, Chandra Chekuri, Samuel Fiorini, Shubhang Kulkarni, Stefan Weltge


  • Approximating Submodular \({k}\)-Partition via Principal Partition Sequence

    by Karthekeyan Chandrasekaran, Weihang Wang

    In 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

    by Karthekeyan Chandrasekaran, Yuri Faenza, Chengyue He, Jay Sethuraman

    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.