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), Lawqueen Kanesh (NUS), Fahad Panolan (IIT Hyderabad), Daniel Lokshtanov (UC Santa Barbara), Saket Saurabh (University of Bergen and Institute of Mathematical Sciences), Meirav Zehavi (Ben-Gurion University of the Negev)
News:
Sid Gupta joins as postdoc from October 2021!
Publications
[C2] An FPT Algorithm for Elimination Distance to Bounded Degree Graphs
Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
STACS 2021.
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.
[C1] On the Parameterized Complexity of Clique Elimination Distance
Akanksha 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]
Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
STACS 2021.
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.
[C1] On the Parameterized Complexity of Clique Elimination Distance
Akanksha 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]
