19 citations · 22 across the 6 of their papers we have counts for
12 papers
An iterative rounding -approximation for Feedback Vertex Set via AI-assisted proof of an extreme point property
Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni
We consider the Feedback Vertex Set problem (FVS): the input is an undirected graph and the goal is to find a minimum-cardinality (or a min-cost in the weighted case) sub…
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 applicatio…
On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni
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 with non…
From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
Chandra Chekuri, Rhea Jain, Shubhang Kulkarni +2
In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph , a root vertex and a set of terminals. The goal is to find…
Hypergraph Connectivity Augmentation in Strongly Polynomial Time
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
We consider hypergraph network design problems where the goal is to construct a hypergraph that satisfies certain connectivity requirements. For graph network design problems where…
Splitting-off in Hypergraphs
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
The splitting-off operation in undirected graphs is a fundamental reduction operation that detaches all edges incident to a given vertex and adds new edges between the neighbors of…
Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
Karthekeyan Chandrasekaran, Chandra Chekuri, Samuel Fiorini +2
We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph with non-negative vertex costs. The goal is to find a mini…
Efficient Feedback and Partial Credit Grading for Proof Blocks Problems
Seth Poulsen, Shubhang Kulkarni, Geoffrey Herman +1
Proof Blocks is a software tool that allows students to practice writing mathematical proofs by dragging and dropping lines instead of writing proofs from scratch. Proof Blocks off…
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate +3
A heapable sequence is a sequence of numbers that can be arranged in a "min-heap data structure". Finding a longest heapable subsequence of a given sequence was proposed by Byers,…
Locally Decodable/Correctable Codes for Insertions and Deletions
Alexander R. Block, Jeremiah Blocki, Elena Grigorescu +2
Recent efforts in coding theory have focused on building codes for insertions and deletions, called insdel codes, with optimal trade-offs between their redundancy and their error-c…
On Locally Decodable Codes in Resource Bounded Channels
Jeremiah Blocki, Shubhang Kulkarni, Samson Zhou
Constructions of locally decodable codes (LDCs) have one of two undesirable properties: low rate or high locality (polynomial in the length of the message). In settings where the e…
The Maximum Binary Tree Problem
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate +3
We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree…