Here is a link to my dblp page.
2021
[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: We study knockout tournaments played among coalitions, allowing each of them to strategically select one of their members to take part in a single-elimination knockout tournament. We investigate the algorithmic properties of equilibrium strategies under various setups, i.e., whether or not choices can be made at each round and whether or not tournament progression is important to the group. The results we obtain can be applied to all those settings where each side participating in a tournament can act strategically before matches take place, such as sport events or elections with run-off.
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. Our main result is a polynomial kernelization (parameterized by the modulator size) for this problem. As components in the proof of our main result, we develop a fixed-parameter algorithm for computing the elimination distance of a given graph to cluster graphs and a polynomial-time polyopt-factor approximation for the same problem.
[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
25th Annual European Symposium on Algorithms (ESA 2017) (Kirk Pruhs, Christian Sohler, eds.), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 57:1–57:15, 2017, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[C40] Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable
M. S. Ramanujan, Stefan Szeider
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pages 3929–3935, 2017.
[C39] Lossy kernelization
Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224–237, 2017.
[C38] Combining Treewidth and Backdoors for CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) (Heribert Vollmer, Brigitte Vallée, eds.), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1–36:17, 2017, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[C37] Backdoor Treewidth for SAT
Robert Ganian, M. S. Ramanujan, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings (Serge Gaspers, Toby Walsh, eds.), volume 10491 of Lecture Notes in Computer Science, pages 20–37, 2017, Springer Verlag.
[C36] Path-Contractions, Edge Deletions and Connectivity Preservation
Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström
25th Annual European Symposium on Algorithms (ESA 2017) (Kirk Pruhs, Christian Sohler, eds.), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1–47:13, 2017, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[C35] Going Beyond Primal Treewidth for (M)ILP
Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., pages 815–821, 2017.
[C34] Saving Critical Nodes with Firefighters is FPT
Jayesh Choudhari, Anirban Dasgupta, Neeldhara Misra, M. S. Ramanujan
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) (Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, Anca Muscholl, eds.), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 135:1–135:13, 2017, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[C33] Linear Representation of Transversal Matroids and Gammoids parameterized by rank
Fahad Panolan, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
Computing and Combinatorics: 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings (Yixin Cao, Jianer Chen, eds.), pages 420–432, 2017, Springer International Publishing.
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
Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers, pages 269–281, 2016.
[C31] A Parameterized Algorithm for Mixed-Cut
Ashutosh Rai, M. S. Ramanujan, Saket Saurabh
LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, pages 672–685, 2016.
[C30] Strong Parameterized Deletion: Bipartite Graphs
Ashutosh Rai, M. S. Ramanujan
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, December 13-15, 2016, Chennai, India, pages 21:1–21:14, 2016.
[C29] Backdoors for Linear Temporal Logic
Arne Meier, Sebastian Ordyniak, M. S. Ramanujan, Irena Schindler
11th International Symposium on Parameterized and Exact Computation (IPEC 2016) (Jiong Guo, Danny Hermelin, eds.), volume 63 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:17, 2016, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[C28] Backdoors to Tractable Valued CSP
Robert Ganian, M. S. Ramanujan., Stefan Szeider
Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings (Michel Rueher, ed.), volume 9892 of Lecture Notes in Computer Science, pages 233–250, 2016, Springer Verlag.
[C27] Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Robert Ganian, M. S. Ramanujan, Stefan Szeider
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1670–1681, 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
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 176–184, 2016.
[C25] On the Complexity Landscape of Connected f-factor Problems
Robert Ganian, N.S. Narayanaswamy, Sebastian Ordyniak, C.S. Rahul, M. S. Ramanujan
Mathematical Foundations of Computer Science 2016 - 41st International Symposium, MFCS 2016 (Piotr Faliszewski, Anca Muscholl, Rolf Niedermeier, eds.), pages 41:1–41:14, 2016, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
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
Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, pages 566–577, 2015.
[C23] Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 935–946, 2015.
[C22] Reconfiguration on Sparse Graphs
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, pages 506–517, 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
IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 963–974, 2015.
[C20] Solving d-SAT via Backdoors to Small Treewidth
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 630–641, 2015.
[C19] Metric Dimension of Bounded Width Graphs
Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan
Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, pages 115–126, 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
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1739–1748, 2014.
Summary: See [J11].
[C17] Vertex Exponential Algorithms for Connected f-Factors
Geevarghese Philip, M. S. Ramanujan
34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India, pages 61–71, 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
Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, pages 457–468, 2014.
Summary: See [J23]
[C15] On the Kernelization Complexity of String Problems
Manu Basavaraju, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan, Saket Saurabh
Computing and Combinatorics - 20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings, pages 141–153, 2014.
[C14] Parameterized Algorithms to Preserve Connectivity
Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 800–811, 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
Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, pages 255–267, 2013.
[C12] Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark Jones, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Ondrej Suchý
Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 671–682, 2013.
[C11] Backdoors to q-Horn
Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, Stefan Szeider
30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany (Natacha Portier, Thomas Wilke, eds.), volume 20 of LIPIcs, pages 67-79, 2013, Leibniz-Zentrum fuer Informatik.
[C10] Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
Jason Crampton, Robert Crowston, Gregory Gutin, Mark Jones, M. S. Ramanujan
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Third Joint International Conference, FAW-AAIM 2013, Dalian, China, June 26-28, 2013. Proceedings, pages 198–209, 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
Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, pages 150–162, 2013.
[C8] Partially Polynomial Kernels for Set Cover and Test Cover
Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, Saket Saurabh
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12-14, 2013, Guwahati, India, pages 67–78, 2013.
2012
[C7] LP can be a cure for Parameterized Problems
N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, pages 338–349, 2012.
[C6] Parameterized Algorithms for Even Cycle Transversal
Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
Graph-Theoretic Concepts in Computer Science - 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selcted Papers, pages 172–183, 2012.
[C5] Parameterized Tractability of Multiway Cut with Parity Constraints
Daniel Lokshtanov, M. S. Ramanujan
Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, pages 750–761, 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
Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, pages 382–393, 2011.
[C2] A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings, pages 333–343, 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
Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings, pages 14–25, 2010.
2021
[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: We study knockout tournaments played among coalitions, allowing each of them to strategically select one of their members to take part in a single-elimination knockout tournament. We investigate the algorithmic properties of equilibrium strategies under various setups, i.e., whether or not choices can be made at each round and whether or not tournament progression is important to the group. The results we obtain can be applied to all those settings where each side participating in a tournament can act strategically before matches take place, such as sport events or elections with run-off.
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. Our main result is a polynomial kernelization (parameterized by the modulator size) for this problem. As components in the proof of our main result, we develop a fixed-parameter algorithm for computing the elimination distance of a given graph to cluster graphs and a polynomial-time polyopt-factor approximation for the same problem.
[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
25th Annual European Symposium on Algorithms (ESA 2017) (Kirk Pruhs, Christian Sohler, eds.), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 57:1–57:15, 2017, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[C40] Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable
M. S. Ramanujan, Stefan Szeider
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pages 3929–3935, 2017.
[C39] Lossy kernelization
Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224–237, 2017.
[C38] Combining Treewidth and Backdoors for CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) (Heribert Vollmer, Brigitte Vallée, eds.), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1–36:17, 2017, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[C37] Backdoor Treewidth for SAT
Robert Ganian, M. S. Ramanujan, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings (Serge Gaspers, Toby Walsh, eds.), volume 10491 of Lecture Notes in Computer Science, pages 20–37, 2017, Springer Verlag.
[C36] Path-Contractions, Edge Deletions and Connectivity Preservation
Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström
25th Annual European Symposium on Algorithms (ESA 2017) (Kirk Pruhs, Christian Sohler, eds.), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1–47:13, 2017, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[C35] Going Beyond Primal Treewidth for (M)ILP
Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., pages 815–821, 2017.
[C34] Saving Critical Nodes with Firefighters is FPT
Jayesh Choudhari, Anirban Dasgupta, Neeldhara Misra, M. S. Ramanujan
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) (Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, Anca Muscholl, eds.), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 135:1–135:13, 2017, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[C33] Linear Representation of Transversal Matroids and Gammoids parameterized by rank
Fahad Panolan, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
Computing and Combinatorics: 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings (Yixin Cao, Jianer Chen, eds.), pages 420–432, 2017, Springer International Publishing.
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
Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers, pages 269–281, 2016.
[C31] A Parameterized Algorithm for Mixed-Cut
Ashutosh Rai, M. S. Ramanujan, Saket Saurabh
LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, pages 672–685, 2016.
[C30] Strong Parameterized Deletion: Bipartite Graphs
Ashutosh Rai, M. S. Ramanujan
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, December 13-15, 2016, Chennai, India, pages 21:1–21:14, 2016.
[C29] Backdoors for Linear Temporal Logic
Arne Meier, Sebastian Ordyniak, M. S. Ramanujan, Irena Schindler
11th International Symposium on Parameterized and Exact Computation (IPEC 2016) (Jiong Guo, Danny Hermelin, eds.), volume 63 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:17, 2016, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[C28] Backdoors to Tractable Valued CSP
Robert Ganian, M. S. Ramanujan., Stefan Szeider
Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings (Michel Rueher, ed.), volume 9892 of Lecture Notes in Computer Science, pages 233–250, 2016, Springer Verlag.
[C27] Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Robert Ganian, M. S. Ramanujan, Stefan Szeider
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1670–1681, 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
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 176–184, 2016.
[C25] On the Complexity Landscape of Connected f-factor Problems
Robert Ganian, N.S. Narayanaswamy, Sebastian Ordyniak, C.S. Rahul, M. S. Ramanujan
Mathematical Foundations of Computer Science 2016 - 41st International Symposium, MFCS 2016 (Piotr Faliszewski, Anca Muscholl, Rolf Niedermeier, eds.), pages 41:1–41:14, 2016, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
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
Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, pages 566–577, 2015.
[C23] Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 935–946, 2015.
[C22] Reconfiguration on Sparse Graphs
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, pages 506–517, 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
IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 963–974, 2015.
[C20] Solving d-SAT via Backdoors to Small Treewidth
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 630–641, 2015.
[C19] Metric Dimension of Bounded Width Graphs
Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan
Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, pages 115–126, 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
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1739–1748, 2014.
Summary: See [J11].
[C17] Vertex Exponential Algorithms for Connected f-Factors
Geevarghese Philip, M. S. Ramanujan
34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India, pages 61–71, 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
Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, pages 457–468, 2014.
Summary: See [J23]
[C15] On the Kernelization Complexity of String Problems
Manu Basavaraju, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan, Saket Saurabh
Computing and Combinatorics - 20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings, pages 141–153, 2014.
[C14] Parameterized Algorithms to Preserve Connectivity
Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 800–811, 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
Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, pages 255–267, 2013.
[C12] Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark Jones, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Ondrej Suchý
Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 671–682, 2013.
[C11] Backdoors to q-Horn
Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, Stefan Szeider
30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany (Natacha Portier, Thomas Wilke, eds.), volume 20 of LIPIcs, pages 67-79, 2013, Leibniz-Zentrum fuer Informatik.
[C10] Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
Jason Crampton, Robert Crowston, Gregory Gutin, Mark Jones, M. S. Ramanujan
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Third Joint International Conference, FAW-AAIM 2013, Dalian, China, June 26-28, 2013. Proceedings, pages 198–209, 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
Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, pages 150–162, 2013.
[C8] Partially Polynomial Kernels for Set Cover and Test Cover
Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, Saket Saurabh
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12-14, 2013, Guwahati, India, pages 67–78, 2013.
2012
[C7] LP can be a cure for Parameterized Problems
N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, pages 338–349, 2012.
[C6] Parameterized Algorithms for Even Cycle Transversal
Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
Graph-Theoretic Concepts in Computer Science - 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selcted Papers, pages 172–183, 2012.
[C5] Parameterized Tractability of Multiway Cut with Parity Constraints
Daniel Lokshtanov, M. S. Ramanujan
Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, pages 750–761, 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
Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, pages 382–393, 2011.
[C2] A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings, pages 333–343, 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
Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings, pages 14–25, 2010.
