Jayakrishnan Madathil

I am a postdoctoral research associate in the School of Computing Science at the University of Glasgow, where I am part of the Beyond One Solution in Combinatorial Optimisation project led by Kitty Meeks. Before moving to Glasgow, I was a postdoc at the Chennai Mathematical Institute, and briefly an Early Career Fellow at IIT Gandhinagar. I did my PhD at The Institute of Mathematical Sciences (IMSc), Chennai.

I am a theoretical computer scientist, broadly interested in algorithms and complexity. I work primarily in parameterized complexity. A part of my current work deals with designing parameterized algorithms for counting problems. I also have an interest in problems at the intersection of economics and computation, specifically, fair allocation problems, mechanism design etc.

News and Updates

New Pre-print: Parameterized Algorithms for Balanced Cluster Edge Modification Problems

with Kitty Meeks
arXiv

Serving as a thesis writing mentor during Feb-June 2024. You can read about University of Glasgow's thesis mentoring programme here.

Extended abstract accepted to AAMAS 2024: Opinion Diffusion on Society Graphs Based on Approval Ballots

with Neeldhara Misra and Yash More

I gave a talk on "Fair Division of a Graph into Compact Bundles" at the Joint Glasgow-Edinburgh Algorithms Workshop, June 2023.

Publications

Click on arrows to expand. Also availabe at dblp and Google Scholar.

Fair Division of a Graph into Compact Bundles

IJCAI 2023
arXiv
Talk (10 min video, external link)

Fair division of graphs typically deals with allocating the vertices of a graph to agents so that the allocation is fair and the subgraph induced by each agent's bundle is connected. Instead of connectivity, we introduce a new constraint---called compactness---on the agents' bundles, and design efficient algorithms for computing fair and compact allocations. The new constraint of compactness attempts to capture the requirement that the items received by each agent be close to one another.

The Complexity of Minimizing Envy in House Allocation (Extended Abstract)

with Neeldhara Misra and Aditi Sethia
AAMAS 2023

We study almost-envy-freeness in house allocation, where we have to allocate m houses to n agents so that each agent receives exactly one house. While we can check in polynomial time if an envy-free allocation exists, an envy-free allocation need not always exist, which prompts the question whether relaxations of envy-freeness can be achieved. But typical relaxations of envy-freeness such as envy-free up to some goods do not make sense for house allocation problems as every agent is required to receive exactly one house. Hence we quantify the envy caused by an allocation using three different metrics---the number of envious agents, the maximum envy experienced by an agent and the total envy experienced by all the agents, and study the complexities of the corresponding computational problems where we are looking for an allocation that minimizes one of the three metrics.

Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems

with Lawqueen Kanesh, Sanjukta Roy, Abhishek Sahu and Saket Saurabh
STACS 2022
SIDMA 2023

Inspired by the triadic closure property exhibited by social networks, Fox, Roughgarden, Seshadhri, Wei and Wein introduced the class of c-closed graphs as a deterministic model of social networks [ICALP 2018 and SICOMP 2020]. A graph G is c-closed if any two distinct vertices with at least c common neighbours are adjacent to each other. Koana, Komusiewicz and Sommer showed that several W-hard problems, including Independent Set and Dominating Set, admit FPT algorithms and polynomial kernels on graphs of bounded closure [ESA 2020 and SIDMA 2022]. Following this work, we study the parameterized complexity of domination problems such as Perfect Code (dominate every vertex exactly once), Connected Dominating Set (dominating set that induces a connected subgraph) and Partial Dominating Set (dominate at least a given number of vertices) on graphs of bounded closure.

A Polynomial Kernel for Bipartite Permutation Vertex Deletion.
- with Jan Derbisz, Lawqueen Kanesh, Abhishek Sahu, Saket Saurabh and Shaily Verma
- IPEC 2021
- Algorithmica, 2022
Odd Cycle Transversal in Mixed Graphs
- with Avinandan Das, Lawqueen Kanesh and Saket Saurabh
- WG 2021

On the Complexity of Singly Connected Vertex Deletion
- with Avinandan Das, Lawqueen Kanesh, Komal Muluk, Nidhi Purohit and Saket Saurabh
- IWOCA 2020
- Theoretical Computer Science, 2022

A Sub-Exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs
- with Roohani Sharma and Meirav Zehavi
- MFCS 2019
- Algorithmica, 2021
Parameterized Complexity Classification of Deletion to List Matrix-Partition for Low-Order Matrices
- with Akanksha Agrawal, Sudeshna Kolay and Saket Saurabh
- ISAAC 2019
On the Complexity of Mixed Dominating Set
- with Fahad Panolan, Abhishek Sahu and Saket Saurabh
- CSR 2019
Connecting the Dots (with Minimum Crossings)
- with Akanksha Agrawal, Grzegorz Guspiel, Saket Saurabh and Meirav Zehavi
- SoCG 2019
An Erdős-Pósa Theorem on Neighborhoods and Domination Number
- with Pranabendu Misra and Saket Saurabh
- COCOON 2019

Max-Cut Above Spanning Tree is Fixed-Parameter Tractable
- with Saket Saurabh and Meirav Zehavi
- CSR 2018 (Best Paper Award)
- Theory of Computing Systems, 2020 (retitled: Fixed-Parameter Tractable Algorithm and Polynomial Kernel for Max-Cut Above Spanning Tree)

Mixed Dominating Set: A Parameterized Perspective
- with Pallavi Jain, Fahad Panolan and Abhishek Sahu
- WG 2017

Contact

You can reach me via email: firstname [dot] lastname [at] glasgow [dot] ac [dot] uk