Arrow Research search

Author name cluster

Karthekeyan Chandrasekaran

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

TCS Journal 2026 Journal Article

Approximating submodular matroid-constrained partitioning

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

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.

Details DOI

SODA Conference 2022 Conference Paper

Deterministic enumeration of all minimum k-cut-sets in hypergraphs for fixed k

  • Calvin Beideman
  • Karthekeyan Chandrasekaran
  • Weihang Wang 0002

We consider the problem of deterministically enumerating all minimum k -cut-sets in a given hypergraph for any fixed k. The input here is a hypergraph G = ( V, E ) with non-negative hyperedge costs. A subset F ⊆ E of hyperedges is a k -cut-set if the number of connected components in G – F is at least k and it is a minimum k -cut-set if it has the least cost among all k -cut-sets. For fixed k, we call the problem of finding a minimum k -cut-set as H ypergraph - k -C ut and the problem of enumerating all minimum k -cut-sets as E num -H ypergraph - k -C ut. The special cases of H ypergraph - k -C ut and E num -H ypergraph - k -C ut restricted to graph inputs are well-known to be solvable in (randomized as well as deterministic) polynomial time [17, 25, 28, 39]. In contrast, it is only recently that polynomial-time algorithms for H ypergraph - k -C ut were developed [2, 3, 12]. The randomized polynomial-time algorithm for H ypergraph - k -C ut that was designed in 2018 [3] showed that the number of minimum k -cut-sets in a hypergraph is O ( n 2 k –2 ), where n is the number of vertices in the input hypergraph, and that they can all be enumerated in randomized polynomial time, thus resolving E num -H ypergraph - k -C ut in randomized polynomial time. A deterministic polynomial-time algorithm for H ypergraph - k -C ut was subsequently designed in 2020 [2], but it is not guaranteed to enumerate all minimum k -cut-sets. In this work, we give the first deterministic polynomial-time algorithm to solve E num -H ypergraph - k -C ut (this is non-trivial even for k = 2). Our algorithm is based on new structural results that allow for efficient recovery of all minimum k -cut-sets by solving minimum ( S, T )-terminal cuts. Our techniques give new structural insights even for enumerating all minimum cut-sets (i. e. , minimum 2-cut-sets) in a given hypergraph.

Details

SODA Conference 2021 Conference Paper

Min-max Partitioning of Hypergraphs and Symmetric Submodular Functions

  • Karthekeyan Chandrasekaran
  • Chandra Chekuri

We consider the complexity of minmax partitioning of graphs, hypergraphs and (symmetric) submodular functions. Our main result is an algorithm for the problem of partitioning the ground set of a given symmetric submodular function f: 2 V → ℝ into k non-empty parts V 1, V 2, …, V k to minimize. Our algorithm runs in time, where n = | V | and T is the time to evaluate f on a given set; hence. this yields a polynomial time algorithm for any fixed k in the evaluation oracle model. As an immediate corollary, for any fixed k, there is a polynomial-time algorithm for the problem of partitioning the vertex set of a given hypergraph H = ( V, E ) into k non-empty parts to minimize the maximum capacity of the parts. The complexity of this problem. termed M inmax -H ypergraph - k -P art, was raised by Lawler in 1973 [16]. In contrast to our positive result, the reduction in [6] implies that when k is part of the input, M inmax -H ypergraph - k -P art is hard to approximate to within an almost polynomial factor under the Exponential Time Hypothesis (ETH).

Details

FOCS Conference 2020 Conference Paper

Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time

  • Karthekeyan Chandrasekaran
  • Chandra Chekuri

We consider the Hypergraph- k-Cut problem. The input consists of a hypergraph G = (V, E) with nonnegative hyperedge-costs c: E→ \mathbbR+ and a positive integer k. The objective is to find a least-cost subset F ⊆ E such that the number of connected components in G-F is at least k. An alternative formulation of the objective is to find a partition of V into k non-empty sets V1, V2, .. ., Vk so as to minimize the cost of the hyperedges that cross the partition. Graph- k-Cut, the special case of Hypergraph- k-Cut obtained by restricting to graph inputs, has received considerable attention. Several different approaches lead to a polynomial-time algorithm for Graph- k-Cut when k is fixed, starting with the work of Goldschmidt and Hochbaum (1988) [1], [2]. In contrast, it is only recently that a randomized polynomial time algorithm for Hypergraph- k-Cut was developed [3] via a subtle generalization of Karger's random contraction approach for graphs. In this work, we develop the first deterministic polynomial time algorithm for Hypergraph- k-Cut for all fixed k. We describe two algorithms both of which are based on a divide and conquer approach. The first algorithm is simpler and runs in n O(k2 ) time while the second one runs in n O(k) time. Our proof relies on new structural results that allow for efficient recovery of the parts of an optimum k-partition by solving minimum ( S, T) -terminal cuts. Our techniques give new insights even for Graph- k-Cut.

Details

MFCS Conference 2019 Conference Paper

Spectral Aspects of Symmetric Matrix Signings

  • Charlie Carlson
  • Karthekeyan Chandrasekaran
  • Hsien-Chih Chang
  • Naonori Kakimura
  • Alexandra Kolla

The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of finding symmetric signings of matrices with natural spectral properties. Our results are the following: 1) We characterize matrices that have an invertible signing: a symmetric matrix has an invertible symmetric signing if and only if the support graph of the matrix contains a perfect 2-matching. Further, we present an efficient algorithm to search for an invertible symmetric signing. 2) We use the above-mentioned characterization to give an algorithm to find a minimum increase in the support of a given symmetric matrix so that it has an invertible symmetric signing. 3) We show NP-completeness of the following problems: verifying whether a given matrix has a symmetric signing that is singular or has bounded eigenvalues. However, we also illustrate that the complexity could differ substantially for input matrices that are adjacency matrices of graphs. We use combinatorial techniques in addition to classic results from matching theory.

Details

FOCS Conference 2012 Conference Paper

The Cutting Plane Method Is Polynomial for Perfect Matchings

  • Karthekeyan Chandrasekaran
  • László A. Végh
  • Santosh S. Vempala

The cutting plane approach to optimal matchings has been discussed by several authors over the past decades, and its rate of convergence has been an open question. We prove that the cutting plane approach using Edmonds' blossom inequalities converges in polynomial time for the minimum-cost perfect matching problem. Our main insight is an LP-based method to select cutting planes. This cut selection procedure leads to a sequence of intermediate linear programs with a linear number of constraints whose optima are half-integral and supported by a disjoint union of odd cycles and edges. This structural property of the optima is instrumental in finding violated blossom inequalities (cuts) in linear time. Moreover, the number of cycles in the support of the half-integral optima acts as a potential function to show efficient convergence to an integral solution.

Details

SODA Conference 2011 Conference Paper

Algorithms for Implicit Hitting Set Problems

  • Karthekeyan Chandrasekaran
  • Richard M. Karp
  • Erick Moreno-Centeno
  • Santosh S. Vempala

A hitting set for a collection of sets is a set that has a nonempty intersection with each set in the collection; the hitting set problem is to find a hitting set of minimum cardinality. Motivated by instances of the hitting set problem where the number of sets to be hit is large, we introduce the notion of implicit hitting set problems. In an implicit hitting set problem the collection of sets to be hit is typically too large to list explicitly; instead, an oracle is provided which, given a set H, either determines that H is a hitting set or returns a set that H does not hit. We show a number of examples of classic implicit hitting set problems, and give a generic algorithm for solving such problems optimally. The main contribution of this paper is to show that this framework is valuable in developing approximation algorithms. We illustrate this methodology by presenting a simple on-line algorithm for the minimum feedback vertex set problem on random graphs. In particular our algorithm gives a feedback vertex set of size n –(1/ p ) log np (1 − o (1)) with probability at least 3/4 for the random graph G n, p (the smallest feedback vertex set is of size n − (2/ p ) log np (1 + o (1))). We also consider a planted model for the feedback vertex set in directed random graphs. Here we show that a hitting set for a polynomial-sized subset of cycles is a hitting set for the planted random graph and this allows us to exactly recover the planted feedback vertex set.

Details
v2026.09.13