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
[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 Groups
Paul 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 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]
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 Groups
Paul 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 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]
