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.
- 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.- with Neeldhara Misra and Yash More
- AAMAS 2024
Opinion Diffusion on Society Graphs Based on Approval Ballots (Extended Abstract)
Imagine an election: there are voters and candidates, and different subsets of voters may like different subsets of candidates. But during the course of the campaign, voters may be influenced by their peers, and change their opinions about the candidates. Could this shift in opinions result in a particular candidate's victory or defeat?
- with Neeldhara Misra and Aditi Sethia
- AAMAS 2023
The Complexity of Minimizing Envy in House Allocation (Extended Abstract)
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.
- with Lawqueen Kanesh, Sanjukta Roy, Abhishek Sahu and Saket Saurabh
- STACS 2022
- SIDMA 2023
Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
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