Here is a link to my dblp page.
2024
[C72] Meta-theorems for Parameterized Streaming Algorithms
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
SODA 2024.
Summary: In this paper, we prove foundational results in the intersection of streaming algorithms and parameterized complexity. We introduce a novel notion of fixed-parameter semi-streaming (FPSS) algorithms that are restricted to run in space O(f(k).n.polylog(n)) and show that several central graph problems in parameterized complexity have FPSS algorithms. This is achieved through a new framework for designing streaming algorithms for classic cut problems (e.g., multiway cut, graph bipartization) and two meta-theorems. Informally stated, the meta-theorems say that:
(i) The Vertex Deletion problem to any class characterized by a finite set of forbidden induced subgraphs has an FPSS algorithm if and only if graphs characterized in this way can be recognized by a semi-streaming algorithms. This has implications for problems such as Feedback Vertex Set in tournaments.
(ii) The Vertex Deletion problem to any class has an FPSS algorithm if graphs in the class have a semi-streaming algorithm that supports edge queries. This has implications for problems such as deletion to block graphs, where the forbidden family of induced subgraphs is infinite.
[C71] Exponential-time Approximation Schemes via Compression
Tanmay Inamdar, Madhumita Kundu, M. S. Ramanujan, Saket Saurabh
ITCS 2024.
Summary: In this paper, we give a framework to design exponential-time approximation schemes for basic graph partitioning problems such as k-way cut, Multiway Cut, Steiner k-cut and Multicut, where the goal is to minimize the number of edges going across the parts. Our motivation to focus on approximation schemes for these problems comes from the fact that while it is possible to solve them exactly in 2^n time (which is already faster than brute-forcing over all partitions or edge sets), it is not known whether one can do better. Using our framework, we design the first (1 + ε)-approximation algorithms for the above problems that run in time 2^{f(ε)n} (for f(ε) < 1) for all these problems. These algorithms are inspired by Karger's randomized contraction algorithm and Benczúr and Karger's work on cut sparsifiers.
[C70] Decremental Sensitivity Oracles for Covering and Packing Minors
Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Peter Strulo
STACS 2024
Summary: In this paper, we present the first decremental fixed-parameter sensitivity oracles for a number of basic covering and packing problems on graphs. These results are obtained as a corollary of our central result, which is the first decremental sensitivity oracle for Topological Minor Deletion (cover all topological minors in the input graph that belong to a specified set, using k vertices).
[C69] An Exercise in Tournament Design: When Some Matches Must Be Scheduled
Sushmita Gupta, M. S. Ramanujan, Peter Strulo
AAAI 2024
Summary: Single-elimination (SE) tournaments are a popular format used in competitive environments and decision making. In this paper, we initiate the algorithmic study of a novel variant of SE tournament manipulation that aims to model the fact that certain matchups are highly desired in a sporting context, incentivizing an organizer to manipulate the bracket to make such matchups take place. We show that while the problem of computing a bracket enforcing a given set of matches in an SE tournament is NP- hard, there are natural restrictions that lead to polynomial- time solvability. In particular, we show polynomial-time solvability if there is a linear ordering on the ability of players with only a constant number of exceptions where a player with lower ability beats a player with higher ability.
2023
[C68] FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less
Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, M. S. Ramanujan, Saket Saurabh
FSTTCS 2023.
[C67] Approximately Interpolating between Uniformly and Non-uniformly Polynomial Kernels
Akanksha Agrawal, M. S. Ramanujan
FSTTCS 2023.
[C66] Finding a Highly Connected Steiner Subgraph and its Applications
Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan
MFCS 2023.
[C65] Identifying and Eliminating Majority Illusion in Social Networks
Umberto Grandi, Lawqueen Kanesh, Grzegorz Lisowski, M. S. Ramanujan, Paolo Turrini
AAAI 2023.
2022
[C64] 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.
[C63] An Exact Algorithm for Knot-Free Vertex Deletion
M. S. Ramanujan, Abhishek Sahu, Saket Saurabh, Shaily Verma
MFCS 2022
[C62] On the Lossy Kernelization for Connected Treedepth Deletion Set
Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan
WG 2022
[C61] Equilibrium Computation for Knockout Tournaments Played by Groups
Paul Harrenstein, Grzegorz Lisowski, M. S. Ramanujan, Paolo Turrini
AAMAS 2022.
[C60] 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.
2021
[C59] On Approximate Compressions for Connected Minor-Hitting Sets
M. S. Ramanujan
ESA 2021
Summary: In this paper, we give the first constant-factor Polynomial-size Approximate Kernelization for the Connected Planar-F Deletion problem. The crux of this result is a proof that for any small ε, given graph G and a non-negative integer k, there is a polynomial-time computable data structure D of size poly(k) such that for every c ≥ 1, if one could extract a c-approximate solution of size at most k from D (for a different problem), then one can obtain a c·(2+ε)-approximate solution for the main problem on G.
[C58] 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.
[C57] FPT-approximation for FPT problems
Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
SODA 2021
Summary: In this paper, we design FPT-approximation algorithms for several problems that are fixed-parameter tractable, with running times that are significantly faster than the corresponding best known FPT-algorithm, and while achieving approximation ratios that are significantly better than what is possible in polynomial time. For instance, we obtain a factor-2 FPT-approximation
for Directed Feedback Vertex Set where the running time has a single-exponential dependence on the parameter.
[C56] 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.
2020
[J24] A New Perspective on FO Model Checking of Dense Graph Classes
Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Daniel Lokshtanov, M. S. Ramanujan
ACM Trans. Comput. Log.21(4): 28:1-28:23 (2020)
[J23] Faster Graph Bipartization
Sudeshna Kolay, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
J. Comput. Syst. Sci. 109: 45-55 (2020)
Summary: The main result of this paper is an FPT algorithm for Graph Bipartization (Odd Cycle Transversal) that has linear dependence on the input size while matching the dependence on k incurred by the algorithm of Reed, Smith and Vetta up to poly(k) factors. This is the current fastest linear-time FPT algorithm for this problem. The crux of this algorithm is a new polynomial-time factor-poly(OPT) approximation for Graph Bipartization that has linear dependence on the input size.
[J22] A Characterization of König-Egerváry graphs with Extendable Vertex Covers.
Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
Information Processing Letters, Vol. 161 (2020)
Summary: It is well known that in a bipartite (and more generally in a König-Egerváry) graph, the size of the minimum vertex cover is equal to the size of the maximum matching. We address the question whether (and if not, when) this property still holds in a König-Egerváry graph if we consider vertex covers containing a given subset of vertices. In this paper, we characterize such graphs using the classic notions of alternating paths and flowers used in Edmonds' matching algorithm.
[J21] On the Approximate Compressibility of Connected Vertex Cover
Diptapriyo Majumdar, M. S. Ramanujan, Saket Saurabh:
Algorithmica 82(10): 2902-2926 (2020)
[J20] Alternative parameterizations of Metric Dimension
Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström
Theor. Comput. Sci. 806: 133-143 (2020)
[C55] Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
SODA 2020
Summary: The Odd Cycle Transversal problem is a fundamental problem in graph algorithmics and resolving the parameterized complexity of the directed version of this problem was one of the biggest open problems in the area of parameterized complexity for more than a decade. In this paper, we resolve this problem by showing that the Directed Odd Cycle Transversal Problem cannot have an efficient parameterized algorithm under reasonable complexity hypotheses.
[C54] On the Complexity of Recovering Incidence Matrices
Fedor V. Fomin, Petr Golovach, Pranabendu Misra, M. S. Ramanujan
ESA 2020
Summary: We initiate the study of the computational complexity of recovering incidence matrices of graphs from a binary matrix that is known to be a small rank or small Hamming weight perturbation of an incidence matrix. We obtain upper and lower bounds when the question asks to recover incidence matrices of graphs from various specific graph classes.
[Conference Talk]
[C53] 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]
[C52] On the Parameterized Complexity of Deletion to H-free Strong Components
Rian Neogi, M. S. Ramanujan, Saket Saurabh, Roohani Sharma
MFCS 2020
Summary: In this paper, we introduce a generalization of the Directed Feedback Vertex Set problem and prove its fixed-parameter tractability. Known FPT results for DFVS, 1-Out-Regular Vertex Deletion and Bounded Size Strong Component Vertex Deletion follow as corollaries.
[Conference Talk]
2019
[J19] On Approximate Preprocessing for Domination and Hitting Subgraphs with Connected Deletion Sets
Eduard Eiben, Danny Hermelin, M. S. Ramanujan
J. Comput. Syst. Sci. (2019). https://doi.org/10.1016/j.jcss.2019.05.001
[J18] On the Complexity Landscape of Connected f-factor Problems
Robert Ganian, N.S. Narayanaswamy, Sebastian Ordyniak, C.S. Rahul, M. S. Ramanujan
Algorithmica 81(6): 2606-2632 (2019)
[C51] An Approximate Kernel for Connected Feedback Vertex Set
M. S. Ramanujan
ESA 2019
Summary: In this paper, we give the first Polynomial-size Approximate Kernelization Scheme (PSAKS) for the Connected Feedback Vertex Set problem. The crux of this result is a proof that for any small ε, given graph G and a non-negative integer k, there is a polynomial-time computable graph G′ of size poly(k) such that for every c ≥ 1, any c-approximate solution for the Connected Feedback Vertex Set problem on G′ of size at most k is a c·(1+ε)-approximate solution for the same problem on G.
[C50] On Succinct Encodings for the Tournament Fixing Problem
Sushmita Gupta, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
IJCAI 2019
Summary: In this paper, we present the first polynomial kernelization for the Tournament Fixing Problem parameterized by the feedback arc set number of the input tournament. We achieve this by providing a polynomial-time SAT encoding where the number of clauses is bounded polynomially in the feedback arc set number.
2018
[J17] Linear Representation of Transversal Matroids and Gammoids parameterized by rank
Fahad Panolan, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
Theoretical Computer Science. (2018). https://doi.org/10.1016/j.tcs.2018.02.029
[J16] Path-Contractions, Edge Deletions and Connectivity Preservation
Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström
J. Comput. Syst. Sci. (2018). https://doi.org/10.1016/j.jcss.2018.10.001
[J15] Backdoors for Linear Temporal Logic
Arne Meier, Sebastian Ordyniak, M. S. Ramanujan, Irena Schindler
Algorithmica (2018). https://doi.org/10.1007/s00453-018-0515-5
[J14] On the Kernelization Complexity of String Problems
Manu Basavaraju, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan, Saket Saurabh
Theoretical Computer Science, Volume 730, 19 June 2018, Pages 21-31
[J13] Reconfiguration on Sparse Graph Classes
Daniel Lokshtanov, Amer Mouawad, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
J. Comput. Syst. Sci., volume 95, pages 122–131, 2018.
[J12] Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
ACM Trans. Algorithms, 14(1): 7:1-7:37 (2018)
[C49] On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
Fedor V. Fomin, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
ESA 2018
[C48] Reducing CMSO Model Checking to Highly Connected Graphs
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
ICALP 2018
[C47] A When Recursion is Better than Iteration: A Linear Time Algorithm for Acyclicity with Few Error Vertices
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
SODA 2018
Summary: This paper settled one of the outstanding open problems regarding the complexity of exactly solving
the classic Feedback Vertex Set problem on directed graphs, leading to the first significant progress on the problem in a decade.
This paper presents a new linear-time algorithm to determine whether a constant number of vertices intersect all feedback loops in a given directed graph, for any given constant. The existence of such an algorithm even when the given constant is 2, was open since '78 [Garey and Tarjan, IPL 78]. The techniques introduced in this work also give faster algorithms for several basic computational problems via a speed-up of the popular and highly cited iterative-compression tool introduced by Reed, Smith and Vetta.
[C46] Parameterized Algorithms for Survivable Network Design with Uniform Demands
Jørgen Bang-Jensen, Manu Basavaraju, Kristine zitting Klinkby, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
SODA 2018
2017
[J11] Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
M. S. Ramanujan, Saket Saurabh
ACM Trans. Algorithms, volume 13, number 4, pages 46:1–46:25, September 2017, Assoc. Comput. Mach., New York.
Summary: This paper presents a linear-time algorithm to determine whether a constant number of vertices intersect all odd cycles in a given undirected graph, for any given constant. This paper introduced new flow-cut techniques on skew-symmetric digraphs and resolved a decade-long open problem resulting from the work of Reed, Smith and Vetta in 2003, where they gave a quadratic-time algorithm (indeed this was the first ever polynomial-time algorithm for this problem).
[J10] Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark Jones, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Ondrej Suchý
SIAM J. Discrete Math., volume 31, number 2, pages 1294–1327, 2017.
[J9] Hitting (Selected) Odd Cycles
Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
SIAM J. Discrete Math., volume 31, number 3, pages 1581–1615, 2017.
[J8] Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Robert Ganian, M. S. Ramanujan, Stefan Szeider
ACM Transactions on Algorithms, volume 13, number 2, pages 29:1–29:32, 2017.
[J7] Faster exact algorithms for some terminal set problems
Rajesh Chitnis, Fedor V. Fomin, Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
J. Comput. Syst. Sci., volume 88, pages 195–207, 2017.
[J6] Metric Dimension of Bounded Tree-length Graphs
Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan
SIAM J. Discrete Math., volume 31, number 2, pages 1217–1243, 2017.
[C45] On Structural Paramerizations of the Edge Disjoint Paths Problem
Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan
ISAAC 2017
[C44] Lossy Kernels for Hitting Subgraphs
Eduard Eiben, Danny Hermelin, M. S. Ramanujan
MFCS 2017
[C43] Towards a Polynomial Kernel for Directed Feedback Vertex Set
Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan
MFCS 2017
[C42] On the Parameterized Complexity of Simultaneous Deletion Problems
Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad, M. S. Ramanujan
FSTTCS 2017
[C41] A Linear-Time Parameterized Algorithm for Node Unique Label Cover
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
ESA 2017
[C40] Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable
M. S. Ramanujan, Stefan Szeider
AAAI 2017
[C39] Lossy kernelization
Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
STOC 2017
[C38] Combining Treewidth and Backdoors for CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
STACS 2017
[C37] Backdoor Treewidth for SAT
Robert Ganian, M. S. Ramanujan, Stefan Szeider
SAT 2017
[C36] Path-Contractions, Edge Deletions and Connectivity Preservation
Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström
ESA 2017
[C35] Going Beyond Primal Treewidth for (M)ILP
Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan
AAAI 2017
[C34] Saving Critical Nodes with Firefighters is FPT
Jayesh Choudhari, Anirban Dasgupta, Neeldhara Misra, M. S. Ramanujan
ICALP 2017
[C33] Linear Representation of Transversal Matroids and Gammoids parameterized by rank
Fahad Panolan, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
COCOON 2017
2016
[J5] Backdoors to q-Horn
Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, Stefan Szeider
Algorithmica, volume 74, number 1, pages 540–557, 2016.
[J4] Partially Polynomial Kernels for Set Cover and Test Cover
Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, Saket Saurabh
SIAM J. Discrete Math., volume 30, number 3, pages 1401–1423, 2016.
[C32] A Faster Parameterized Algorithm for Group Feedback Edge Set
M. S. Ramanujan
WG 2016
[C31] A Parameterized Algorithm for Mixed-Cut
Ashutosh Rai, M. S. Ramanujan, Saket Saurabh
LATIN 2016:
[C30] Strong Parameterized Deletion: Bipartite Graphs
Ashutosh Rai, M. S. Ramanujan
FSTTCS 2016
[C29] Backdoors for Linear Temporal Logic
Arne Meier, Sebastian Ordyniak, M. S. Ramanujan, Irena Schindler
IPEC 2016
[C28] Backdoors to Tractable Valued CSP
Robert Ganian, M. S. Ramanujan., Stefan Szeider
CP 2016
[C27] Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Robert Ganian, M. S. Ramanujan, Stefan Szeider
SODA 2016
[C26] A New Perspective on FO Model Checking of Dense Graph Classes
Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Daniel Lokshtanov, M. S. Ramanujan
LICS 2016
[C25] On the Complexity Landscape of Connected f-factor Problems
Robert Ganian, N.S. Narayanaswamy, Sebastian Ordyniak, C.S. Rahul, M. S. Ramanujan
MFCS 2016
2015
[J3] Faster Parameterized Algorithms for Deletion to Split Graphs
Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan
Algorithmica, volume 71, number 4, pages 989–1006, 2015.
[C24] On the Parameterized Complexity of Girth and Connectivity Problems on Linear Matroids
Fahad Panolan, M. S. Ramanujan, Saket Saurabh
WADS 2015
[C23] Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
ICALP 2015
[C22] Reconfiguration on Sparse Graphs
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
WADS 2015
[C21] FO Model Checking on Posets of Bounded Width
Jakub Gajarský, Petr Hlinený, Daniel Lokshtanov, Jan Obdrzálek, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh
FOCS 2015
[C20] Solving d-SAT via Backdoors to Small Treewidth
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh
SODA 2015
[C19] Metric Dimension of Bounded Width Graphs
Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan
MFCS 2015
2014
[J2] Faster Parameterized Algorithms Using Linear Programming
Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
ACM Transactions on Algorithms, volume 11, number 2, pages 15:1–15:31, 2014.
Summary: This paper is the first to beat the 3^k dependence on the parameter in fixed-parameter algorithms for the classic Odd Cycle Transversal problem. The importance of this paper is threefold: (i) The 3^k bound had survived for ten years and there was belief that this could be tight. (ii) It was among the earliest papers to bring linear-programming (LP) techniques to the design of fixed-parameter algorithms. LP techniques are now a cornerstone of fixed-parameter algorithm design. (iii) It provides the current best parameter dependence for this problem.
[C18] Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
M. S. Ramanujan, Saket Saurabh
SODA 2014
Summary: See [J11].
[C17] Vertex Exponential Algorithms for Connected f-Factors
Geevarghese Philip, M. S. Ramanujan
FSTTCS 2014
Summary: In this paper we present the first vertex-exponential algorithms for the problem of finding a connected f-factor. The techniques used therein are extended to obtain an algorithm (with similar running time) to compute a max-weight Eulerian subgraph in a given graph.
[C16] Parameterized Approximations via d-Skew-Symmetric Multicut
Sudeshna Kolay, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
MFCS 2014
Summary: See [J23]
[C15] On the Kernelization Complexity of String Problems
Manu Basavaraju, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan, Saket Saurabh
COCOON 2014
[C14] Parameterized Algorithms to Preserve Connectivity
Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
ICALP 2014
2013
[J1] A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
Theory Comput. Syst., volume 53, number 4, pages 609–620, 2013.
[C13] Hardness of r-dominating set on Graphs of Diameter (r + 1)
Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, M. S. Ramanujan, Saket Saurabh
IPEC 2013
[C12] Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark Jones, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Ondrej Suchý
ESA 2013
[C11] Backdoors to q-Horn
Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, Stefan Szeider
STACS 2013
[C10] Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
Jason Crampton, Robert Crowston, Gregory Gutin, Mark Jones, M. S. Ramanujan
FAW-AAIM 2013
[C9] Faster Exact Algorithms for Some Terminal Set Problems
Rajesh Hemant Chitnis, Fedor V. Fomin, Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
IPEC 2013
[C8] Partially Polynomial Kernels for Set Cover and Test Cover
Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, Saket Saurabh
FSTTCS 2013
2012
[C7] LP can be a cure for Parameterized Problems
N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
STACS 2012
[C6] Parameterized Algorithms for Even Cycle Transversal
Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
WG 2012
[C5] Parameterized Tractability of Multiway Cut with Parity Constraints
Daniel Lokshtanov, M. S. Ramanujan
ICALP 2012
[C4] Faster Parameterized Algorithms for Deletion Split Graphs
Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan:
SWAT 2012.
2011
[C3] Paths, Flowers and Vertex Cover
Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
ESA 2011
[C2] A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
ISAAC 2011
2010
[C1] On the Kernelization Complexity of Colorful Motifs
Abhimanyu M. Ambalath, Radheshyam Balasundaram, Chintan Rao H., Venkata Koppula, Neeldhara Misra, Geevarghese Philip, M. S. Ramanujan
IPEC 2010
2024
[C72] Meta-theorems for Parameterized Streaming Algorithms
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
SODA 2024.
Summary: In this paper, we prove foundational results in the intersection of streaming algorithms and parameterized complexity. We introduce a novel notion of fixed-parameter semi-streaming (FPSS) algorithms that are restricted to run in space O(f(k).n.polylog(n)) and show that several central graph problems in parameterized complexity have FPSS algorithms. This is achieved through a new framework for designing streaming algorithms for classic cut problems (e.g., multiway cut, graph bipartization) and two meta-theorems. Informally stated, the meta-theorems say that:
(i) The Vertex Deletion problem to any class characterized by a finite set of forbidden induced subgraphs has an FPSS algorithm if and only if graphs characterized in this way can be recognized by a semi-streaming algorithms. This has implications for problems such as Feedback Vertex Set in tournaments.
(ii) The Vertex Deletion problem to any class has an FPSS algorithm if graphs in the class have a semi-streaming algorithm that supports edge queries. This has implications for problems such as deletion to block graphs, where the forbidden family of induced subgraphs is infinite.
[C71] Exponential-time Approximation Schemes via Compression
Tanmay Inamdar, Madhumita Kundu, M. S. Ramanujan, Saket Saurabh
ITCS 2024.
Summary: In this paper, we give a framework to design exponential-time approximation schemes for basic graph partitioning problems such as k-way cut, Multiway Cut, Steiner k-cut and Multicut, where the goal is to minimize the number of edges going across the parts. Our motivation to focus on approximation schemes for these problems comes from the fact that while it is possible to solve them exactly in 2^n time (which is already faster than brute-forcing over all partitions or edge sets), it is not known whether one can do better. Using our framework, we design the first (1 + ε)-approximation algorithms for the above problems that run in time 2^{f(ε)n} (for f(ε) < 1) for all these problems. These algorithms are inspired by Karger's randomized contraction algorithm and Benczúr and Karger's work on cut sparsifiers.
[C70] Decremental Sensitivity Oracles for Covering and Packing Minors
Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Peter Strulo
STACS 2024
Summary: In this paper, we present the first decremental fixed-parameter sensitivity oracles for a number of basic covering and packing problems on graphs. These results are obtained as a corollary of our central result, which is the first decremental sensitivity oracle for Topological Minor Deletion (cover all topological minors in the input graph that belong to a specified set, using k vertices).
[C69] An Exercise in Tournament Design: When Some Matches Must Be Scheduled
Sushmita Gupta, M. S. Ramanujan, Peter Strulo
AAAI 2024
Summary: Single-elimination (SE) tournaments are a popular format used in competitive environments and decision making. In this paper, we initiate the algorithmic study of a novel variant of SE tournament manipulation that aims to model the fact that certain matchups are highly desired in a sporting context, incentivizing an organizer to manipulate the bracket to make such matchups take place. We show that while the problem of computing a bracket enforcing a given set of matches in an SE tournament is NP- hard, there are natural restrictions that lead to polynomial- time solvability. In particular, we show polynomial-time solvability if there is a linear ordering on the ability of players with only a constant number of exceptions where a player with lower ability beats a player with higher ability.
2023
[C68] FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less
Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, M. S. Ramanujan, Saket Saurabh
FSTTCS 2023.
[C67] Approximately Interpolating between Uniformly and Non-uniformly Polynomial Kernels
Akanksha Agrawal, M. S. Ramanujan
FSTTCS 2023.
[C66] Finding a Highly Connected Steiner Subgraph and its Applications
Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan
MFCS 2023.
[C65] Identifying and Eliminating Majority Illusion in Social Networks
Umberto Grandi, Lawqueen Kanesh, Grzegorz Lisowski, M. S. Ramanujan, Paolo Turrini
AAAI 2023.
2022
[C64] 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.
[C63] An Exact Algorithm for Knot-Free Vertex Deletion
M. S. Ramanujan, Abhishek Sahu, Saket Saurabh, Shaily Verma
MFCS 2022
[C62] On the Lossy Kernelization for Connected Treedepth Deletion Set
Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan
WG 2022
[C61] Equilibrium Computation for Knockout Tournaments Played by Groups
Paul Harrenstein, Grzegorz Lisowski, M. S. Ramanujan, Paolo Turrini
AAMAS 2022.
[C60] 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.
2021
[C59] On Approximate Compressions for Connected Minor-Hitting Sets
M. S. Ramanujan
ESA 2021
Summary: In this paper, we give the first constant-factor Polynomial-size Approximate Kernelization for the Connected Planar-F Deletion problem. The crux of this result is a proof that for any small ε, given graph G and a non-negative integer k, there is a polynomial-time computable data structure D of size poly(k) such that for every c ≥ 1, if one could extract a c-approximate solution of size at most k from D (for a different problem), then one can obtain a c·(2+ε)-approximate solution for the main problem on G.
[C58] 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.
[C57] FPT-approximation for FPT problems
Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
SODA 2021
Summary: In this paper, we design FPT-approximation algorithms for several problems that are fixed-parameter tractable, with running times that are significantly faster than the corresponding best known FPT-algorithm, and while achieving approximation ratios that are significantly better than what is possible in polynomial time. For instance, we obtain a factor-2 FPT-approximation
for Directed Feedback Vertex Set where the running time has a single-exponential dependence on the parameter.
[C56] 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.
2020
[J24] A New Perspective on FO Model Checking of Dense Graph Classes
Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Daniel Lokshtanov, M. S. Ramanujan
ACM Trans. Comput. Log.21(4): 28:1-28:23 (2020)
[J23] Faster Graph Bipartization
Sudeshna Kolay, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
J. Comput. Syst. Sci. 109: 45-55 (2020)
Summary: The main result of this paper is an FPT algorithm for Graph Bipartization (Odd Cycle Transversal) that has linear dependence on the input size while matching the dependence on k incurred by the algorithm of Reed, Smith and Vetta up to poly(k) factors. This is the current fastest linear-time FPT algorithm for this problem. The crux of this algorithm is a new polynomial-time factor-poly(OPT) approximation for Graph Bipartization that has linear dependence on the input size.
[J22] A Characterization of König-Egerváry graphs with Extendable Vertex Covers.
Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
Information Processing Letters, Vol. 161 (2020)
Summary: It is well known that in a bipartite (and more generally in a König-Egerváry) graph, the size of the minimum vertex cover is equal to the size of the maximum matching. We address the question whether (and if not, when) this property still holds in a König-Egerváry graph if we consider vertex covers containing a given subset of vertices. In this paper, we characterize such graphs using the classic notions of alternating paths and flowers used in Edmonds' matching algorithm.
[J21] On the Approximate Compressibility of Connected Vertex Cover
Diptapriyo Majumdar, M. S. Ramanujan, Saket Saurabh:
Algorithmica 82(10): 2902-2926 (2020)
[J20] Alternative parameterizations of Metric Dimension
Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström
Theor. Comput. Sci. 806: 133-143 (2020)
[C55] Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
SODA 2020
Summary: The Odd Cycle Transversal problem is a fundamental problem in graph algorithmics and resolving the parameterized complexity of the directed version of this problem was one of the biggest open problems in the area of parameterized complexity for more than a decade. In this paper, we resolve this problem by showing that the Directed Odd Cycle Transversal Problem cannot have an efficient parameterized algorithm under reasonable complexity hypotheses.
[C54] On the Complexity of Recovering Incidence Matrices
Fedor V. Fomin, Petr Golovach, Pranabendu Misra, M. S. Ramanujan
ESA 2020
Summary: We initiate the study of the computational complexity of recovering incidence matrices of graphs from a binary matrix that is known to be a small rank or small Hamming weight perturbation of an incidence matrix. We obtain upper and lower bounds when the question asks to recover incidence matrices of graphs from various specific graph classes.
[Conference Talk]
[C53] 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]
[C52] On the Parameterized Complexity of Deletion to H-free Strong Components
Rian Neogi, M. S. Ramanujan, Saket Saurabh, Roohani Sharma
MFCS 2020
Summary: In this paper, we introduce a generalization of the Directed Feedback Vertex Set problem and prove its fixed-parameter tractability. Known FPT results for DFVS, 1-Out-Regular Vertex Deletion and Bounded Size Strong Component Vertex Deletion follow as corollaries.
[Conference Talk]
2019
[J19] On Approximate Preprocessing for Domination and Hitting Subgraphs with Connected Deletion Sets
Eduard Eiben, Danny Hermelin, M. S. Ramanujan
J. Comput. Syst. Sci. (2019). https://doi.org/10.1016/j.jcss.2019.05.001
[J18] On the Complexity Landscape of Connected f-factor Problems
Robert Ganian, N.S. Narayanaswamy, Sebastian Ordyniak, C.S. Rahul, M. S. Ramanujan
Algorithmica 81(6): 2606-2632 (2019)
[C51] An Approximate Kernel for Connected Feedback Vertex Set
M. S. Ramanujan
ESA 2019
Summary: In this paper, we give the first Polynomial-size Approximate Kernelization Scheme (PSAKS) for the Connected Feedback Vertex Set problem. The crux of this result is a proof that for any small ε, given graph G and a non-negative integer k, there is a polynomial-time computable graph G′ of size poly(k) such that for every c ≥ 1, any c-approximate solution for the Connected Feedback Vertex Set problem on G′ of size at most k is a c·(1+ε)-approximate solution for the same problem on G.
[C50] On Succinct Encodings for the Tournament Fixing Problem
Sushmita Gupta, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
IJCAI 2019
Summary: In this paper, we present the first polynomial kernelization for the Tournament Fixing Problem parameterized by the feedback arc set number of the input tournament. We achieve this by providing a polynomial-time SAT encoding where the number of clauses is bounded polynomially in the feedback arc set number.
2018
[J17] Linear Representation of Transversal Matroids and Gammoids parameterized by rank
Fahad Panolan, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
Theoretical Computer Science. (2018). https://doi.org/10.1016/j.tcs.2018.02.029
[J16] Path-Contractions, Edge Deletions and Connectivity Preservation
Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström
J. Comput. Syst. Sci. (2018). https://doi.org/10.1016/j.jcss.2018.10.001
[J15] Backdoors for Linear Temporal Logic
Arne Meier, Sebastian Ordyniak, M. S. Ramanujan, Irena Schindler
Algorithmica (2018). https://doi.org/10.1007/s00453-018-0515-5
[J14] On the Kernelization Complexity of String Problems
Manu Basavaraju, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan, Saket Saurabh
Theoretical Computer Science, Volume 730, 19 June 2018, Pages 21-31
[J13] Reconfiguration on Sparse Graph Classes
Daniel Lokshtanov, Amer Mouawad, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
J. Comput. Syst. Sci., volume 95, pages 122–131, 2018.
[J12] Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
ACM Trans. Algorithms, 14(1): 7:1-7:37 (2018)
[C49] On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
Fedor V. Fomin, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
ESA 2018
[C48] Reducing CMSO Model Checking to Highly Connected Graphs
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
ICALP 2018
[C47] A When Recursion is Better than Iteration: A Linear Time Algorithm for Acyclicity with Few Error Vertices
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
SODA 2018
Summary: This paper settled one of the outstanding open problems regarding the complexity of exactly solving
the classic Feedback Vertex Set problem on directed graphs, leading to the first significant progress on the problem in a decade.
This paper presents a new linear-time algorithm to determine whether a constant number of vertices intersect all feedback loops in a given directed graph, for any given constant. The existence of such an algorithm even when the given constant is 2, was open since '78 [Garey and Tarjan, IPL 78]. The techniques introduced in this work also give faster algorithms for several basic computational problems via a speed-up of the popular and highly cited iterative-compression tool introduced by Reed, Smith and Vetta.
[C46] Parameterized Algorithms for Survivable Network Design with Uniform Demands
Jørgen Bang-Jensen, Manu Basavaraju, Kristine zitting Klinkby, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
SODA 2018
2017
[J11] Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
M. S. Ramanujan, Saket Saurabh
ACM Trans. Algorithms, volume 13, number 4, pages 46:1–46:25, September 2017, Assoc. Comput. Mach., New York.
Summary: This paper presents a linear-time algorithm to determine whether a constant number of vertices intersect all odd cycles in a given undirected graph, for any given constant. This paper introduced new flow-cut techniques on skew-symmetric digraphs and resolved a decade-long open problem resulting from the work of Reed, Smith and Vetta in 2003, where they gave a quadratic-time algorithm (indeed this was the first ever polynomial-time algorithm for this problem).
[J10] Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark Jones, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Ondrej Suchý
SIAM J. Discrete Math., volume 31, number 2, pages 1294–1327, 2017.
[J9] Hitting (Selected) Odd Cycles
Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
SIAM J. Discrete Math., volume 31, number 3, pages 1581–1615, 2017.
[J8] Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Robert Ganian, M. S. Ramanujan, Stefan Szeider
ACM Transactions on Algorithms, volume 13, number 2, pages 29:1–29:32, 2017.
[J7] Faster exact algorithms for some terminal set problems
Rajesh Chitnis, Fedor V. Fomin, Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
J. Comput. Syst. Sci., volume 88, pages 195–207, 2017.
[J6] Metric Dimension of Bounded Tree-length Graphs
Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan
SIAM J. Discrete Math., volume 31, number 2, pages 1217–1243, 2017.
[C45] On Structural Paramerizations of the Edge Disjoint Paths Problem
Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan
ISAAC 2017
[C44] Lossy Kernels for Hitting Subgraphs
Eduard Eiben, Danny Hermelin, M. S. Ramanujan
MFCS 2017
[C43] Towards a Polynomial Kernel for Directed Feedback Vertex Set
Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan
MFCS 2017
[C42] On the Parameterized Complexity of Simultaneous Deletion Problems
Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad, M. S. Ramanujan
FSTTCS 2017
[C41] A Linear-Time Parameterized Algorithm for Node Unique Label Cover
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
ESA 2017
[C40] Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable
M. S. Ramanujan, Stefan Szeider
AAAI 2017
[C39] Lossy kernelization
Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
STOC 2017
[C38] Combining Treewidth and Backdoors for CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
STACS 2017
[C37] Backdoor Treewidth for SAT
Robert Ganian, M. S. Ramanujan, Stefan Szeider
SAT 2017
[C36] Path-Contractions, Edge Deletions and Connectivity Preservation
Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström
ESA 2017
[C35] Going Beyond Primal Treewidth for (M)ILP
Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan
AAAI 2017
[C34] Saving Critical Nodes with Firefighters is FPT
Jayesh Choudhari, Anirban Dasgupta, Neeldhara Misra, M. S. Ramanujan
ICALP 2017
[C33] Linear Representation of Transversal Matroids and Gammoids parameterized by rank
Fahad Panolan, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
COCOON 2017
2016
[J5] Backdoors to q-Horn
Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, Stefan Szeider
Algorithmica, volume 74, number 1, pages 540–557, 2016.
[J4] Partially Polynomial Kernels for Set Cover and Test Cover
Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, Saket Saurabh
SIAM J. Discrete Math., volume 30, number 3, pages 1401–1423, 2016.
[C32] A Faster Parameterized Algorithm for Group Feedback Edge Set
M. S. Ramanujan
WG 2016
[C31] A Parameterized Algorithm for Mixed-Cut
Ashutosh Rai, M. S. Ramanujan, Saket Saurabh
LATIN 2016:
[C30] Strong Parameterized Deletion: Bipartite Graphs
Ashutosh Rai, M. S. Ramanujan
FSTTCS 2016
[C29] Backdoors for Linear Temporal Logic
Arne Meier, Sebastian Ordyniak, M. S. Ramanujan, Irena Schindler
IPEC 2016
[C28] Backdoors to Tractable Valued CSP
Robert Ganian, M. S. Ramanujan., Stefan Szeider
CP 2016
[C27] Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Robert Ganian, M. S. Ramanujan, Stefan Szeider
SODA 2016
[C26] A New Perspective on FO Model Checking of Dense Graph Classes
Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Daniel Lokshtanov, M. S. Ramanujan
LICS 2016
[C25] On the Complexity Landscape of Connected f-factor Problems
Robert Ganian, N.S. Narayanaswamy, Sebastian Ordyniak, C.S. Rahul, M. S. Ramanujan
MFCS 2016
2015
[J3] Faster Parameterized Algorithms for Deletion to Split Graphs
Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan
Algorithmica, volume 71, number 4, pages 989–1006, 2015.
[C24] On the Parameterized Complexity of Girth and Connectivity Problems on Linear Matroids
Fahad Panolan, M. S. Ramanujan, Saket Saurabh
WADS 2015
[C23] Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
ICALP 2015
[C22] Reconfiguration on Sparse Graphs
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
WADS 2015
[C21] FO Model Checking on Posets of Bounded Width
Jakub Gajarský, Petr Hlinený, Daniel Lokshtanov, Jan Obdrzálek, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh
FOCS 2015
[C20] Solving d-SAT via Backdoors to Small Treewidth
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh
SODA 2015
[C19] Metric Dimension of Bounded Width Graphs
Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan
MFCS 2015
2014
[J2] Faster Parameterized Algorithms Using Linear Programming
Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
ACM Transactions on Algorithms, volume 11, number 2, pages 15:1–15:31, 2014.
Summary: This paper is the first to beat the 3^k dependence on the parameter in fixed-parameter algorithms for the classic Odd Cycle Transversal problem. The importance of this paper is threefold: (i) The 3^k bound had survived for ten years and there was belief that this could be tight. (ii) It was among the earliest papers to bring linear-programming (LP) techniques to the design of fixed-parameter algorithms. LP techniques are now a cornerstone of fixed-parameter algorithm design. (iii) It provides the current best parameter dependence for this problem.
[C18] Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
M. S. Ramanujan, Saket Saurabh
SODA 2014
Summary: See [J11].
[C17] Vertex Exponential Algorithms for Connected f-Factors
Geevarghese Philip, M. S. Ramanujan
FSTTCS 2014
Summary: In this paper we present the first vertex-exponential algorithms for the problem of finding a connected f-factor. The techniques used therein are extended to obtain an algorithm (with similar running time) to compute a max-weight Eulerian subgraph in a given graph.
[C16] Parameterized Approximations via d-Skew-Symmetric Multicut
Sudeshna Kolay, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
MFCS 2014
Summary: See [J23]
[C15] On the Kernelization Complexity of String Problems
Manu Basavaraju, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan, Saket Saurabh
COCOON 2014
[C14] Parameterized Algorithms to Preserve Connectivity
Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
ICALP 2014
2013
[J1] A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
Theory Comput. Syst., volume 53, number 4, pages 609–620, 2013.
[C13] Hardness of r-dominating set on Graphs of Diameter (r + 1)
Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, M. S. Ramanujan, Saket Saurabh
IPEC 2013
[C12] Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark Jones, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Ondrej Suchý
ESA 2013
[C11] Backdoors to q-Horn
Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, Stefan Szeider
STACS 2013
[C10] Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
Jason Crampton, Robert Crowston, Gregory Gutin, Mark Jones, M. S. Ramanujan
FAW-AAIM 2013
[C9] Faster Exact Algorithms for Some Terminal Set Problems
Rajesh Hemant Chitnis, Fedor V. Fomin, Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
IPEC 2013
[C8] Partially Polynomial Kernels for Set Cover and Test Cover
Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, Saket Saurabh
FSTTCS 2013
2012
[C7] LP can be a cure for Parameterized Problems
N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
STACS 2012
[C6] Parameterized Algorithms for Even Cycle Transversal
Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
WG 2012
[C5] Parameterized Tractability of Multiway Cut with Parity Constraints
Daniel Lokshtanov, M. S. Ramanujan
ICALP 2012
[C4] Faster Parameterized Algorithms for Deletion Split Graphs
Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan:
SWAT 2012.
2011
[C3] Paths, Flowers and Vertex Cover
Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
ESA 2011
[C2] A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
ISAAC 2011
2010
[C1] On the Kernelization Complexity of Colorful Motifs
Abhimanyu M. Ambalath, Radheshyam Balasundaram, Chintan Rao H., Venkata Koppula, Neeldhara Misra, Geevarghese Philip, M. S. Ramanujan
IPEC 2010