S. AjaykrishnanE.

activity

20232026

collaborators

8 papers

math.CO2026

Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number

Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +2

A three-path-configuration is a graph consisting of three pairwise internally vertex-disjoint paths, the union of every two of which is an induced cycle of length at least four. A…

math.CO2026

Induced-Minor-Closed Classes have Linear, Square-Root, or Sub-Polynomial Tree-Independence

Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +1

An independent set in a graph $G$ is a set of pairwise non-adjacent vertices. A tree decomposition of $G$ is a pair $(T, χ)$ where $T$ is a tree and $χ : V (T) \to 2^{V (G)}$ …

cs.CG2026

Parameterized Approximation of Rectangle Stabbing

Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov +4

In the Rectangle Stabbing problem, input is a set $R$ of axis-parallel rectangles and a set $L$ of axis parallel lines in the plane. The task is to find a minimum siz…

math.CO2026

Induced Minors and Coarse Tree Decompositions

Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +1

Let $G$ be a graph, $S \subseteq V (G)$ be a vertex set in $G$ and $r$ be a positive integer. The distance $r$ -independence number of $S$ is the size of the largest subset $I \subse…

cs.DS2025

Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division

Ajaykrishnan E S, Daniel Lokshtanov

We study the problem of Envy-Free Incomplete Connected Fair Division, where exactly p vertices of an undirected graph must be allocated to agents such that each agent receives a co…

cs.DS2025

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs

Ajaykrishnan E S, Robert Ganian, Daniel Lokshtanov +1

A graph $G$ is a circle graph if it is an intersection graph of chords of a unit circle. We give an algorithm that takes as input an $n$ vertex circle graph $G$ , runs in time at mo…

math.CO2025

(Treewidth, Clique)-Boundedness and Poly-logarithmic Tree-Independence

Maria Chudnovsky, Ajaykrishnan E S, Daniel Lokshtanov

An independent set in a graph $G$ is a set of pairwise non-adjacent vertices. A tree decomposition of $G$ is a pair $(T, χ)$ where $T$ is a tree and $χ : V (T) \to 2^{V (G)}$ …

cs.DS2023

An Improved Exact Algorithm for Knot-Free Vertex Deletion

Ajaykrishnan E S, Soumen Maity, Abhishek Sahu +1

A knot $K$ in a directed graph $D$ is a strongly connected component of size at least two such that there is no arc $(u, v)$ with $u \in V (K)$ and $v \in / V (K)$ . Given a directed g…