**This page is dedicated to activities funded by the EPSRC New Investigator Award (EP/V007793/1) PARITY: New Frontiers in Parameterizing Away from Triviality.**

Project Summary: This project aims to take a significant stride forward in the area of graph algorithms by formally introducing new and more complex notions of graph edit distance and studying their impact on efficient solvability of NP-hard problems. These notions of edit distance will depend not on the number of edit operations as they traditionally have, but on their inherent structure. The success of parameterized complexity has shown that studying the structure of relevant objects as opposed to only considering their size, can have a powerful impact on efficient solvability of computational problems. In summary, this project will lay the foundations for an advanced algorithmic theory built on "structural edit distances" between graphs, develop new algorithms for fundamental problems and uncover hitherto unknown efficiently solvable instances. The project deals with a fundamental research topic in algorithmics and will contribute towards major advances in this subarea of theoretical computer science.

**Project Staff:**

Ramanujan Sridharan (PI)

__Siddharth Gupta__(Postdoc)

**Collaborators:**

Akanksha Agrawal (IIT Madras), Eduard Eiben (Royal Holloway University of London), Paul Harrenstein (University of Oxford), Lawqueen Kanesh (NUS), Fahad Panolan (IIT Hyderabad), Grzegorz Lisowski (University of Warwick), Daniel Lokshtanov (UC Santa Barbara), Diptapriyo Majumdar (IIIT Delhi), Saket Saurabh (University of Bergen and Institute of Mathematical Sciences), Paolo Turrini (University of Warwick), Meirav Zehavi (Ben-Gurion University of the Negev)

Publications

[

Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan

ICALP 2022

[

Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan

WG 2022

[

Paul Harrenstein, Grzegorz Lisowski, M. S. Ramanujan, Paolo Turrini

AAMAS 2022

[

Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi

SODA 2022

[

Johannes Blum, Yann Disser, Andreas Emil Feldmann, Siddharth Gupta, Anna Zych-Pawlewicz

IPEC 2022

[J1

Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Saket Saurabh

SIAM J. Discret. Math. 36(2): 911-921 (2022)

[

Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, Alexander Wolff

ESA 2022

[

Paul Harrenstein, Grzegorz Lisowski, M. S. Ramanujan, Paolo Turrini

AAMAS 2021

[

Akanksha Agrawal, M. S. Ramanujan

IPEC 2020

**C8] Backdoors on Nowhere Dense SAT**Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan

ICALP 2022

*Summary: In this paper, we show that computing a weak-backdoor set of size k to the class of treewidth-t CNF formulas is FPT as long as the input CNF formula excludes a K_d,d as a subgraph in its incidence graph. The class of graphs excluding K_d,d as a subgraph is a vast class that includes as subclasses, graphs of bounded degeneracy, the class of minor-free graphs, classes of bounded expansion and even nowhere dense graph classes. Thus, we give a strong result for weak-backdoor computation to bounded treewidth formulas that encapsulates inputs satisfying many well-established notions of graph sparsity.*[

**C7] On the Lossy Kernelization for Connected Treedepth Deletion Set**Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan

WG 2022

[

**C6]****Equilibrium Computation for Knockout Tournaments Played by Groups**Equilibrium Computation For Knockout Tournaments Played By GroupsPaul Harrenstein, Grzegorz Lisowski, M. S. Ramanujan, Paolo Turrini

AAMAS 2022

[

**C5] Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-equivalent**Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi

SODA 2022

*Summary: In this paper, we show that the parameterized complexity of computing elimination distance to any hereditary, union-closed graph class is essentially the same as that of computing the standard vertex-deletion distance to the this graph class. This result unifies and extends several recent results in the literature on the recently popular graph parameter -- elimination distance.*[

**C4]****On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension**Johannes Blum, Yann Disser, Andreas Emil Feldmann, Siddharth Gupta, Anna Zych-Pawlewicz

IPEC 2022

[J1

**]****An FPT Algorithm for Elimination Distance to Bounded Degree Graphs**Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Saket Saurabh

SIAM J. Discret. Math. 36(2): 911-921 (2022)

*Summary: In this paper, we show that computing the elimination distance of a given graph to the class of graphs excluding a finite set of graphs as an induced subgraph is fixed-parameter tractable parameterized by the solution value, i.e., the elimination distance. As a corollary, we obtain an FPT algorithm for determining the elimination distance of a given graph to the class of graphs of bounded degree.*

[

**C3]****Bounding and Computing Obstacle Numbers of Graphs**Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, Alexander Wolff

ESA 2022

[

**C2]****A Hotelling-Downs Framework for Party Nominees**Paul Harrenstein, Grzegorz Lisowski, M. S. Ramanujan, Paolo Turrini

AAMAS 2021

*Summary:**In this paper, present a model for the strategic selection of party nominees, where competing groups choose their representatives based on the expected electoral returns. Within this framework we explore the algorithmic properties of Nash equilibria, which are not guaranteed to exist even in two party competitions. Our results readily extend to games with restricted positioning options for the players involved, such as facility location and Voronoi games.*[

**C1**] On the Parameterized Complexity of Clique Elimination DistanceAkanksha Agrawal, M. S. Ramanujan

IPEC 2020

*Summary: In this paper, we consider the problem of computing the elimination distance of a given graph to the class of cluster graphs and initiate the study of the parameterized complexity of a more general version – that of obtaining a modulator to such graphs. Among other results, we develop a fixed-parameter algorithm for computing the elimination distance of a given graph to cluster graphs.***[Conference Talk]**