M. S. Ramanujan 0001

SODA Conference 2025 Conference Paper

Packing Short Cycles

• Matthias Bentert
• Fedor V. Fomin
• Petr A. Golovach
• Tuukka Korhonen
• William Lochet
• Fahad Panolan
• M. S. Ramanujan 0001
• Saket Saurabh 0001

SODA Conference 2024 Conference Paper

Meta-theorems for Parameterized Streaming Algorithms‡

• Daniel Lokshtanov
• Pranabendu Misra
• Fahad Panolan
• M. S. Ramanujan 0001
• Saket Saurabh 0001
• Meirav Zehavi

MFCS Conference 2023 Conference Paper

Finding a Highly Connected Steiner Subgraph and its Applications

• Eduard Eiben
• Diptapriyo Majumdar
• M. S. Ramanujan 0001

Given a (connected) undirected graph G, a set X ⊆ V(G) and integers k and p, the Steiner Subgraph Extension problem asks whether there exists a set S ⊇ X of at most k vertices such that G[S] is a p-edge-connected subgraph. This problem is a natural generalization of the well-studied Steiner Tree problem (set p = 1 and X to be the terminals). In this paper, we initiate the study of Steiner Subgraph Extension from the perspective of parameterized complexity and give a fixed-parameter algorithm (i. e. , FPT algorithm) parameterized by k and p on graphs of bounded degeneracy (removing the assumption of bounded degeneracy results in W-hardness). Besides being an independent advance on the parameterized complexity of network design problems, our result has natural applications. In particular, we use our result to obtain new single-exponential FPT algorithms for several vertex-deletion problems studied in the literature, where the goal is to delete a smallest set of vertices such that: (i) the resulting graph belongs to a specified hereditary graph class, and (ii) the deleted set of vertices induces a p-edge-connected subgraph of the input graph.

MFCS Conference 2022 Conference Paper

An Exact Algorithm for Knot-Free Vertex Deletion

• M. S. Ramanujan 0001
• Abhishek Sahu
• Saket Saurabh 0001
• Shaily Verma

The study of the Knot-Free Vertex Deletion problem emerges from its application in the resolution of deadlocks called knots, detected in a classical distributed computation model, that is, the OR-model. A strongly connected subgraph Q of a digraph D with at least two vertices is said to be a knot if there is no arc (u, v) of D with u ∈ V(Q) and v ∉ V(Q) (no-out neighbors of the vertices in Q). Given a directed graph D, the Knot-Free Vertex Deletion (KFVD) problem asks to compute a minimum-size subset S ⊂ V(D) such that D[V⧵S] contains no knots. There is no exact algorithm known for the KFVD problem in the literature that is faster than the trivial O^⋆(2ⁿ) brute-force algorithm. In this paper, we obtain the first non-trivial upper bound for KFVD by designing an exact algorithm running in time 𝒪^⋆(1. 576ⁿ), where n is the size of the vertex set in D.

SODA Conference 2022 Conference Paper

Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent

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

Vertex-deletion problems have been at the heart of parameterized complexity throughout its history. Here, the aim is to determine the minimum size (denoted by mod ℋ ) of a modulator to a graph class ℋ, i. e. , a set of vertices whose deletion results in a graph in ℋ. Recent years have seen the development of a research programme where the complexity of modulators is measured in ways other than size. For instance, for a graph class ℋ, the graph parameters elimination distance to ℋ (denoted by ed ℋ ) [Bulian and Dawar, Algorithmica, 2016] and ℋ -treewidth (denoted by tw ℋ ) [Eiben et al. JCSS, 2021] aim to minimize the treedepth and treewidth, respectively, of the “torso” of the graph induced on a modulator to the graph class ℋ. Here, the torso of a vertex set S in a graph G is the graph with vertex set S and an edge between two vertices u, v ∊ S if there is a path between u and v in G whose internal vertices all lie outside S. In this paper, we show that from the perspective of (non-uniform) fixed-parameter tractability (FPT), the three parameters described above give equally powerful parameterizations for every hereditary graph class ℋ that satisfies mild additional conditions. In fact, we show that for every hereditary graph class ℋ satisfying mild additional conditions, with the exception of ed ℋ parameterized by tw ℋ, for every pair of these parameters, computing one parameterized by itself or any of the others is FPT-equivalent to the standard vertex-deletion (to ℋ ) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing ed ℋ and tw ℋ. The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if ℋ is hereditary, union-closed, CMSO-definable, and (a) the canonical equivalence relation (or any refinement thereof) for membership in the class can be efficiently computed, or (b) the class admits a “strong irrelevant vertex rule”, then there exists a uniform FPT algorithm for ed ℋ. Using these sufficient conditions, we obtain uniform FPT algorithms for computing ed ℋ, when ℋ is defined by excluding a finite number of connected (a) minors, or (b) topological minors, or (c) induced subgraphs, or when ℋ is any of bipartite, chordal or interval graphs. For most of these problems, the existence of a uniform FPT algorithm has remained open in the literature. In fact, for some of them, even a non-uniform FPT algorithm was not known. For example, Jansen et al. [STOC 2021] ask for such an algorithm when ℋ is defined by excluding a finite number of connected topological minors. We resolve their question in the affirmative.

SODA Conference 2021 Conference Paper

FPT-approximation for FPT Problems

• Daniel Lokshtanov
• Pranabendu Misra
• M. S. Ramanujan 0001
• Saket Saurabh 0001
• Meirav Zehavi

Over the past decade, many results have focused on the design of parameterized approximation algorithms for W[1]-hard problems. However, there are fundamental problems within the class FPT for which the best known algorithms have seen no progress over the course of the decade; some of them have even been proved not to admit algorithms that run in time 2 ( k ) n (1) under the Exponential Time Hypothesis (ETH) or ( c – ∊ ) k n (1) under the Strong ETH (SETH). In this paper, we expand the study of FPT-approximation and initiate a systematic study of FPT-approximation for problems that are FPT. We design FPT-approximation algorithms for problems that are FPT, 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. We present a general scheme to design 2 ( k ) n (1) -time 2-approximation algorithms for cut problems. In particular, we exemplify it for D irected F eedback V ertex S et, D irected S ubset F eedback V ertex S et, D irected O dd C ycle T ransversal and U ndirected M ulticut. Further, we extend our scheme to obtain FPT-time (1)-approximation algorithms for weighted cut problems, where the objective is to obtain a solution of size at most k and of minimum weight. Here, we present two approaches. The first approach achieves 2 ( k ) n (1) -time constant-factor approximation, which we exemplify for all problems mentioned in the first bullet. The other leads to an FPT-approximation Scheme (FPT-AS) for W eighted D irected F eedback V ertex S et. Additionally, we present a combinatorial lemma that yields a partition of the vertex set of a graph to roughly equal sized sets so that the removal of each set reduces its treewidth substantially, which may be of independent interest. For several graph problems, use this lemma to design c w n (1) -time (1 + ∊ )-approximation algorithms that are faster than known SETH lower bounds, where w is the treewidth of the input graph. Examples of such problems include V ertex C over, C omponent O rder C onnectivity, B ounded -D egree V ertex D eletion and ℱ -P acking for any family ℱ of bounded sized graphs. Lastly, we present a general reduction of problems parameterized by treewidth to their versions parameterized by solution size. Combined with our first scheme, we exemplify it to obtain c w n (1) -time bicriteria approximation algorithms for all problems mentioned in the first bullet.

MFCS Conference 2020 Conference Paper

On the Parameterized Complexity of Deletion to ℋ-Free Strong Components

• Rian Neogi
• M. S. Ramanujan 0001
• Saket Saurabh 0001
• Roohani Sharma

Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the ℋ-SCC Deletion problem. Here, one is given a digraph D, an integer k and the objective is to decide whether there is a vertex set of size at most k whose deletion leaves a digraph where every strong component excludes graphs in the fixed finite family ℋ as (not necessarily induced) subgraphs. When ℋ comprises only the digraph with a single arc, then this problem is precisely DFVS. Our main result is a proof that this problem is fixed-parameter tractable parameterized by the size of the deletion set if ℋ only contains rooted graphs or if ℋ contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the recent results of Göke et al. [CIAC 2019] for the 1-Out-Regular Vertex Deletion and Bounded Size Strong Component Vertex Deletion problems. Moreover, we design algorithms for the two above mentioned problems, whose running times are better and match with the best bounds for DFVS, without using the heavy machinery of shadow removal as is done by Göke et al. [CIAC 2019].

SODA Conference 2020 Conference Paper

Parameterized Complexity and Approximability of Directed Odd Cycle Transversal

• Daniel Lokshtanov
• M. S. Ramanujan 0001
• Saket Saurabh 0001
• Meirav Zehavi

A directed odd cycle transversal of a directed graph (digraph) D is a vertex set S that intersects every odd directed cycle of D. In the D irected O dd C ycle T ransversal (DOCT) problem, the input consists of a digraph D and an integer k. The objective is to determine whether there exists a directed odd cycle transversal of D of size at most k. In this paper, we settle the parameterized complexity of DOCT when parameterized by the solution size k by showing that DOCT does not admit an algorithm with running time unless FPT = W[1]. On the positive side, we give a factor 2 fixed-parameter approximation (FPT approximation) algorithm for the problem. More precisely, our algorithm takes as input D and k, runs in time, and either concludes that D does not have a directed odd cycle transversal of size at most k, or produces a solution of size at most 2k. Finally, assuming gap-ETH, we show that there exists an ϵ > 0 such that DOCT does not admit a factor (1 + ϵ ) FPT-approximation algorithm.

SODA Conference 2018 Conference Paper

Parameterized Algorithms for Survivable Network Design with Uniform Demands

• Jørgen Bang-Jensen
• Manu Basavaraju
• Kristine Vitting Klinkby
• Pranabendu Misra
• M. S. Ramanujan 0001
• Saket Saurabh 0001
• Meirav Zehavi

In the S urvivable N etwork D esign P roblem (SNDP), the input is an edge-weighted (di)graph G and an integer r uυ for every pair of vertices u, υ ∊ V ( G ). The objective is to construct a subgraph H of minimum weight which contains r uυ edge-disjoint (or node-disjoint) u-υ paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call λ-E dge C onnected S ubgraph (λ-ECS). In this problem, the input is a λ-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also λ-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace λ-edge connectivity with λ-vertex connectivity we get the λ-V ertex C onnected S ubgraph (λ-VCS) problem. We show that λ-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2 O ( k log k ) | V ( G )| O (1). We follow up on this result and obtain a polynomial compression for λ-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical M inimum E quivalent G raph (MEG) problem. We also show that λ-Ves is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs.

SODA Conference 2018 Conference Paper

When Recursion is Better than Iteration: A Linear-Time Algorithm for Acyclicity with Few Error Vertices

• Daniel Lokshtanov
• M. S. Ramanujan 0001
• Saket Saurabh 0001

Planarity, bipartiteness and (directed) acyclicity are basic graph properties with classic linear time recognition algorithms. However, the problems of testing whether a given (di)graph has k vertices whose deletion makes it planar, bipartite or a directed acyclic graph (DAG) are all fundamental NP-complete problems when k is part of the input. As a result, a significant amount of research has been devoted to understanding whether, for every fixed k, these problems admit a polynomial time algorithm (where the exponent in the polynomial is independent of k ) and in particular, whether they admit linear time algorithms. While we now know that for any fixed k, we can test in linear time whether a graph is k vertices away from being planar [FOCS 2009, SODA 2014] or bipartite [SODA 2014, SICOMP 2016], the best known algorithms in the case of directed acyclicity are the algorithm of Garey and Tarjan [IPL 78] which runs in time O ( n k–1 m ) and the algorithm of Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008] which runs in time O ( k! 4 k k 4 nm ). In other words, it has remained open whether it is possible to recognize in linear time, a graph which is 2 vertices away from being acyclic! In this paper, we settle this question by giving an algorithm that decides whether a given graph is k vertices away from being acyclic, in time O ( k! 4 k k 5 ( n + m )). That is, for every fixed k, our algorithm runs in time O ( m + n), thus mirroring the case for planarity and bipartiteness. Our algorithm is designed via a general methodology that shaves off a factor of n from some algorithms that use the powerful technique of iterative compression. The two main features of our methodology are: (i) This is the first generic technique for designing linear time algorithms for directed cut-problems and (ii) it can be used in combination with future improvements in algorithms for the compression version of other well-studied cut-problems such as M ulticut and D irected S ubset F eedback V ertex S et.

SAT Conference 2017 Conference Paper

Backdoor Treewidth for SAT

• Robert Ganian
• M. S. Ramanujan 0001
• Stefan Szeider

Abstract A strong backdoor in a CNF formula is a set of variables such that each possible instantiation of these variables moves the formula into a tractable class. The algorithmic problem of finding a strong backdoor has been the subject of intensive study, mostly within the parameterized complexity framework. Results to date focused primarily on backdoors of small size. In this paper we propose a new approach for algorithmically exploiting strong backdoors for SAT: instead of focusing on small backdoors, we focus on backdoors with certain structural properties. In particular, we consider backdoors that have a certain tree-like structure, formally captured by the notion of backdoor treewidth. First, we provide a fixed-parameter algorithm for SAT parameterized by the backdoor treewidth w. r. t. the fundamental tractable classes Horn, Anti-Horn, and 2CNF. Second, we consider the more general setting where the backdoor decomposes the instance into components belonging to different tractable classes, albeit focusing on backdoors of treewidth 1 (i. e. , acyclic backdoors). We give polynomial-time algorithms for SAT and #SAT for instances that admit such an acyclic backdoor.

STOC Conference 2017 Conference Paper

Lossy kernelization

• Daniel Lokshtanov
• Fahad Panolan
• M. S. Ramanujan 0001
• Saket Saurabh 0001

In this paper we propose a new framework for analyzing the performance of preprocessing algorithms. Our framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, our definitions com- bine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size α-approximate kernel. Loosely speaking, a polynomial size α-approximate kernel is a polynomial time pre-processing algorithm that takes as input an instance ( I , k ) to a parameterized problem, and outputs another instance ( I ′, k ′) to the same problem, such that | I ′| + k ′ ≤ k O (1) . Additionally, for every c ≥ 1, a c -approximate solution s ′ to the pre-processed instance ( I ′, k ′) can be turned in polynomial time into a ( c · α)-approximate solution s to the original instance ( I , k ). Amongst our main technical contributions are α-approximate kernels of polynomial size for three problems, namely Connected Vertex Cover, Disjoint Cycle Packing and Disjoint Factors. These problems are known not to admit any polynomial size kernels unless NP ⊆ coNP / Poly . Our approximate kernels simultaneously beat both the lower bounds on the (normal) kernel size, and the hardness of approximation lower bounds for all three problems. On the negative side we prove that Longest Path parameterized by the length of the path and Set Cover parameterized by the universe size do not admit even an α-approximate kernel of polynomial size, for any α≥1, unless NP ⊆ coNP / Poly . In order to prove this lower bound we need to combine in a non-trivial way the techniques used for showing kernelization lower bounds with the methods for showing hardness of approximation.

MFCS Conference 2017 Conference Paper

Lossy Kernels for Hitting Subgraphs

• Eduard Eiben
• Danny Hermelin
• M. S. Ramanujan 0001

In this paper, we study the Connected H-hitting Set and Dominating Set problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the Connected H-hitting set problem, we obtain an \alpha-approximate kernel for every \alpha>1 and complement it with a lower bound for the natural weighted version. We then perform a refined analysis of the tradeoff between the approximation factor and kernel size for the Dominating Set problem on d-degenerate graphs and provide an interpolation of approximate kernels between the known d^2-approximate kernel of constant size and 1-approximate kernel of size k^{O(d^2)}.

MFCS Conference 2017 Conference Paper

Towards a Polynomial Kernel for Directed Feedback Vertex Set

• Benjamin Bergougnoux
• Eduard Eiben
• Robert Ganian
• Sebastian Ordyniak
• M. S. Ramanujan 0001

In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008]; since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying undirected graph. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus.

SODA Conference 2016 Conference Paper

Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting

• Robert Ganian
• M. S. Ramanujan 0001
• Stefan Szeider

The Constraint Satisfaction Problem (CSP) is a central and generic computational problem which provides a common framework for many theoretical and practical applications. A central line of research is concerned with the identification of classes of instances for which CSP can be solved in polynomial time; such classes are often called “islands of tractability. ” A prominent way of defining islands of tractability for CSP is to restrict the relations that may occur in the constraints to a fixed set, called a constraint language, whereas a constraint language is conservative if it contains all unary relations. Schaefer's famous Dichotomy Theorem (STOC 1978) identifies all islands of tractability in terms of tractable constraint languages over a Boolean domain of values. Since then many extensions and generalizations of this result have been obtained. Recently, Bulatov (TOCL 2011, JACM 2013) gave a full characterization of all islands of tractability for CSP and the counting version #CSP that are defined in terms of conservative constraint languages. This paper addresses the general limit of the mentioned tractability results for CSP and #CSP, that they only apply to instances where all constraints belong to a single tractable language (in general, the union of two tractable languages isn't tractable). We show that we can overcome this limitation as long as we keep some control of how constraints over the various considered tractable languages interact with each other. For this purpose we utilize the notion of a strong backdoor of a CSP instance, as introduced by Williams et al. (IJCAI 2003), which is a set of variables that when instantiated moves the instance to an island of tractability, i. e. , to a tractable class of instances. We consider strong backdoors into scattered classes, consisting of CSP instances where each connected component belongs entirely to some class from a list of tractable classes. Figuratively speaking, a scattered class constitutes an archipelago of tractability. The main difficulty lies in finding a strong backdoor of given size k; once it is found, we can try all possible instantiations of the backdoor variables and apply the polynomial time algorithms associated with the islands of tractability on the list component wise. Our main result is an algorithm that, given a CSP instance with n variables, finds in time f ( k ) n ℴ (1) a strong backdoor into a scattered class (associated with a list of finite conservative constraint languages) of size k or correctly decides that there isn't such a backdoor. This also gives the running time for solving (#)CSP, provided that (#)CSP is polynomial-time tractable for the considered constraint languages. Our result makes significant progress towards the main goal of the backdoor-based approach to CSPs – the identification of maximal base classes for which small backdoors can be detected efficiently.

MFCS Conference 2016 Conference Paper

On the Complexity Landscape of Connected f-Factor Problems

• Robert Ganian
• N. S. Narayanaswamy
• Sebastian Ordyniak
• C. S. Rahul 0001
• M. S. Ramanujan 0001

Given an n-vertex graph G and a function f: V(G) -> {0, .. ., n-1}, an f-factor is a subgraph H of G such that deg_H(v)=f(v) for every vertex v in V(G); we say that H is a connected f-factor if, in addition, the subgraph H is connected. A classical result of Tutte (1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connected f-factor is easily seen to generalize Hamiltonian Cycle and hence is NP-complete. In fact, the Connected f-Factor problem remains NP-complete even when f(v) is at least n^epsilon for each vertex v and epsilon<1; on the other side of the spectrum, the problem was known to be polynomial-time solvable when f(v) is at least n/3 for every vertex v. In this paper, we extend this line of work and obtain new complexity results based on restricting the function f. In particular, we show that when f(v) is required to be at least n/(log n)^c, the problem can be solved in quasi-polynomial time in general and in randomized polynomial time if c <= 1. We also show that when c>1, the problem is NP-intermediate.

FOCS Conference 2015 Conference Paper

FO Model Checking on Posets of Bounded Width

• Jakub Gajarský
• Petr Hlinený
• Daniel Lokshtanov
• Jan Obdrzálek
• Sebastian Ordyniak
• M. S. Ramanujan 0001
• Saket Saurabh 0001

Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs [STOC'14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [CSL-LICS'14] initiated the study of the complexity of FO model checking on partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking existential FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. We resolve this question in the positive by giving an algorithm that takes as its input an n-element poset P of width w and an FO logic formula φ, and determines whether φ holds on P in time f(φ, w) · n 2.

SODA Conference 2015 Conference Paper

Solving d- SAT via Backdoors to Small Treewidth

• Fedor V. Fomin
• Daniel Lokshtanov
• Neeldhara Misra
• M. S. Ramanujan 0001
• Saket Saurabh 0001

A backdoor set of a CNF formula is a set of variables such that fixing the truth values of the variables from this set moves the formula into a polynomial-time de-cidable class. In this work we obtain several algorithmic results for solving d -SAT, by exploiting backdoors to d -CNF formulas whose incidence graphs have small treewidth. For a CNF formula ϕ and integer t, a strong backdoor set to treewidth t is a set of variables such that each possible partial assignment τ to this set reduces ϕ to a formula whose incidence graph is of treewidth at most t. A weak backdoor set to treewidth t is a set of variables such that there is a partial assignment to this set that reduces ϕ to a satisfiable formula of treewidth at most t. Our main contribution is an algorithm that, given a d -CNF formula ϕ and an integer k, in time, either finds a satisfying assignment of ϕ, or reports correctly that ϕ is not satisfiable, or concludes correctly that ϕ has no weak or strong backdoor set to treewidth t of size at most k. As a consequence of the above, we show that d -SAT parameterized by the size of a smallest weak/strong backdoor set to formulas of treewidth t, is fixed-parameter tractable. Prior to our work, such results were know only for the very special case of t = 1 (Gaspers and Szeider, ICALP 2012). Our result not only extends the previous work, it also improves the running time substantially. The running time of our algorithm is linear in the input size for every fixed k. Moreover, the exponential dependence on the parameter k is asymptotically optimal under Exponential Time Hypothesis (ETH). One of our main technical contributions is a linear time “protrusion replacer” improving over a (n log 2 n )-time procedure of Fomin et al. (FOCS 2012). The new deterministic linear time protrusion replacer has several applications in kernelization and parameterized algorithms.

SODA Conference 2014 Conference Paper

Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts

• M. S. Ramanujan 0001
• Saket Saurabh 0001

A skew-symmetric graph ( D = ( V, A ), σ ) is a directed graph D with an involution σ on the set of vertices and arcs. Flows on skew-symmetric graphs have been used to generalize maximum flow and maximum matching problems on graphs, initially by Tutte [1967], and later by Goldberg and Karzanov [1994, 1995]. In this paper, we introduce a separation problem, d -S kew -S ymmetric M ulticut, where we are given a skew-symmetric graph D, a family of of d -sized subsets of vertices and an integer k. The objective is to decide if there is a set X ⊆ A of k arcs such that every set J in the family has a vertex v such that v and σ ( v ) are in different strongly connected components of D′ = ( V, A \ ( X ∪ σ ( X )). In this paper, we give an algorithm for d -S kew -S ymmetric M ulticut which runs in time ((4 d ) k ( m + n + ℓ )), where m is the number of arcs in the graph, n the number of vertices and ℓ the length of the family given in the input. This problem, apart from being independently interesting, also abstracts out and captures the main combinatorial obstacles towards solving numerous classical problems. Our algorithm for d -S kew -S ymmetric M ulticut paves the way for the first linear time parameterized algorithms for several problems. We demonstrate its utility by obtaining the following linear time parameterized algorithms. We show that A lmost 2-SAT is a special case of 1-S kew -S ymmetric M ulticut, resulting in an algorithm for A lmost 2-SAT which runs in time (4 k k 4 ℓ ) where k is the size of the solution and ℓ is the length of the input formula. Then, using linear time parameter preserving reductions to A lmost 2-SAT, we obtain algorithms for O dd C ycle T ransversal and E dge B ipartization which run in time (4 k k 4 ( m + n )) and (4 k k 5 ( m + n )) respectively where k is size of the solution, m and n are the number of edges and vertices respectively. This resolves an open problem posed by Reed, Smith and Vetta [Operations Research Letters, 2003] and improves upon the earlier almost linear time algorithm of Kawarabayashi and Reed [SODA, 2010]. We show that D eletion q -Horn B ackdoor S et D etection is a special case of 3-S kew -S ymmetric M ulticut, giving us an algorithm for Deletion q -Horn B ackdoor S et D etection which runs in time (12 k k 5 ℓ ) where k is the size of the solution and ℓ is the length of the input formula. This gives the first fixed-parameter tractable algorithm for this problem answering a question posed in a paper by a superset of the authors [STACS, 2013]. Using this result, we get an algorithm for S atisfiability which runs in time (12 k k 5 ℓ ) where k is the size of the smallest q -Horn deletion backdoor set, with ℓ being the length of the input formula.