In the d-Euclidean Distance Matrix Completion (d-EDMC) problem, one aims to determine whether a given partial matrix of pairwise distances can be extended to a full Euclidean distance matrix in d dimensions. This problem is a cornerstone of computational geometry with numerous applications. While classical work on this problem often focuses on exploiting connections to semidefinite programming typically leading to approximation algorithms, we focus on exact algorithms and propose a novel distance-from-triviality parameterization framework to obtain tractability results for d-EDMC. We identify key structural patterns in the input that capture entry density, including chordal substructures and coverability of specified entries by fully specified principal submatrices. We obtain: 1) The first fixed-parameter algorithm (FPT algorithm) for d-EDMC parameterized by d and the maximum number of unspecified entries per row/column. This is achieved through a novel compression algorithm that reduces a given instance to a submatrix on 𝒪(1) rows (for fixed values of the parameters). 2) The first FPT algorithm for d-EDMC parameterized by d and the minimum number of fully specified principal submatrices whose entries cover all specified entries of the given matrix. This result is also achieved through a compression algorithm. 3) A polynomial-time algorithm for d-EDMC when both d and the minimum fill-in of a natural graph representing the specified entries are fixed constants. This result is achieved by combining tools from distance geometry and algorithms from real algebraic geometry. Our work identifies interesting parallels between EDM completion and graph problems, with our algorithms exploiting techniques from both domains.

We present fixed-parameter algorithms (FPT algorithms) for the \(\lambda\)-vertex connectivity augmentation (\(\lambda\)-VCA) problem for all values of \(\lambda \le 4\); that is, we give an algorithm that given a graph \(G\), a set \(L\) of non-edges, and an integer \(k\), determines in time \(k^{\mathcal{O}(k)} \cdot n^{c}\) (for some constant \(c\) independent of \(k\)) whether \(G\) can be made \(\lambda\)-vertex connected by adding at most \(k\) elements from \(L\).

Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths [Björklund and Husfeldt, ICALP 2014; Mari et al., SODA 2024] or request the paths to be shortest [Lochet, SODA 2021], we consider the following cycle packing problems: Min-Sum Cycle Packing and Shortest Cycle Packing . In Min-Sum Cycle Packing , we try to find, in a weighted undirected graph, \( k \) vertex-disjoint cycles of minimum total weight. Our first main result is an algorithm that, for any fixed \( k \) , solves the problem in polynomial time. We complement this result by establishing the W[1]-hardness of Min-Sum Cycle Packing parameterized by \( k \) . The same results hold for the version of the problem where the task is to find \( k \) edge-disjoint cycles. Our second main result concerns Shortest Cycle Packing , which is a special case of Min-Sum Cycle Packing that asks to find a packing of \( k \) shortest cycles in a graph. We prove this problem to be Fixed-Parameter Tractable (FPT) when parameterized by \( k \) on weighted planar graphs. We also obtain a polynomial kernel for the edge-disjoint variant of the problem on planar graphs. Whether Min-Sum Cycle Packing is FPT on planar graphs, or Shortest Cycle Packing on general graphs, remains open.

We study the parameterized complexity of a generalization of the Coordinated Motion Planning (CMP) problem on graphs, where the goal is to route a specified subset of a given set of \( k \) robots to their destinations with the aim of minimizing the total energy (i.e., the total length traveled). We develop novel techniques to push beyond previously established results that were restricted to solid grids. We design a fixed-parameter additive approximation algorithm for this problem parameterized by \( k \) alone. This result, which is of independent interest, allows us to prove the following two results pertaining to well-studied CMP problems: (1) A fixed-parameter algorithm, parameterized by \( k \) , for routing a single robot to its destination while avoiding the other robots, which is related to the famous Rush-Hour Puzzle; and (2) a fixed-parameter algorithm, parameterized by \( k \) plus the treewidth of the input graph, for the standard CMP problem in which we need to route all the \( k \) robots to their destinations. The latter of these results implies, among others, the fixed-parameter tractability of CMP parameterized by \( k \) on graphs of bounded outerplanarity, which include bounded-height subgrids. We complement the above results with a lower bound, which rules out the fixed-parameter tractability for CMP when parameterized by the total energy. This contrasts with the recently obtained tractability of the problem on solid grids under the same parameterization. As our final result, we strengthen the aforementioned fixed-parameter tractability to hold not only on solid grids but all graphs of bounded local treewidth—a class including, among others, all graphs of bounded genus.

Distance geometry explores the properties of distance spaces that can be exactly represented as the pairwise Euclidean distances between points in ℝ^d (d ≥ 1), or equivalently, distance spaces that can be isometrically embedded in ℝ^d. In this work, we investigate whether a distance space can be isometrically embedded in ℝ^d after applying a limited number of modifications. Specifically, we focus on two types of modifications: outlier deletion (removing points) and distance modification (adjusting distances between points). The central problem, Euclidean Embedding Editing, asks whether an input distance space on n points can be transformed, using at most k modifications, into a space that is isometrically embeddable in ℝ^d. We present several fixed-parameter tractable (FPT) and approximation algorithms for this problem. Our first result is an algorithm that solves Euclidean Embedding Editing in time (dk)^𝒪(d+k) + n^𝒪(1). The core subroutine of this algorithm, which is of independent interest, is a polynomial-time method for compressing the input distance space into an equivalent instance of Euclidean Embedding Editing with 𝒪((dk)²) points. For the special but important case of Euclidean Embedding Editing where only outlier deletions are allowed, we improve the parameter dependence of the FPT algorithm and obtain a running time of min{(d+3)^k, 2^{d+k}} ⋅ n^𝒪(1). Additionally, we provide an FPT-approximation algorithm for this problem, which outputs a set of at most 2 ⋅ Opt outliers in time 2^d ⋅ n^{𝒪(1)}. This 2-approximation algorithm improves upon the previous (3+ε)-approximation algorithm by Sidiropoulos, Wang, and Wang [SODA '17]. Furthermore, we complement our algorithms with hardness results motivating our choice of parameterizations.

A module of a graph G is a set of vertices that have the same set of neighbours outside. Modules of a graphs form a so-called partitive family and thereby can be represented by a unique tree MD(G), called the modular decomposition tree. Motivated by the central role of modules in numerous algorithmic graph theory questions, the problem of efficiently computing MD(G) has been investigated since the early 70's. To date the best algorithms run in linear time but are all rather complicated. By combining previous algorithmic paradigms developed for the problem, we are able to present a simpler linear-time that relies on very simple data-structures, namely slice decomposition and sequences of rooted ordered trees.

Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths [Björklund, Husfeldt, ICALP 2014;

In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph is Eulerian. This problem is a natural extension of the Directed Feedback Arc Set problem and is also known to be motivated by certain scenarios arising in the study of housing markets. The complexity of the problem, when parameterized by solution size (i.e., size of the deletion set), has remained unresolved and has been highlighted in several papers. In this work, we answer this question by ruling out (subject to the usual complexity assumptions) a fixed-parameter algorithm (FPT algorithm) for this parameter and conduct a broad analysis of the problem with respect to other natural parameterizations. We prove both positive and negative results. Among these, we demonstrate that the problem is also hard (W[1]-hard or even para-NP-hard) when parameterized by either treewidth or maximum degree alone. Complementing our lower bounds, we establish that the problem is in XP when parameterized by treewidth and FPT when parameterized either by both treewidth and maximum degree or by both treewidth and solution size. We show that on simple digraphs, these algorithms have near-optimal asymptotic dependence on the treewidth assuming the Exponential Time Hypothesis.

Majority illusion occurs in a social network when the majority of the network vertices belong to a certain type but the majority of each vertex's neighbours belong to a different type, therefore creating the wrong perception, i.e., the illusion, that the majority type is different from the actual one. From a system engineering point of view, this motivates the search for algorithms to detect and, where possible, correct this often undesirable phenomenon. In this we provide a computational study of majority illusion in social networks, paying particular attention to the problem of its verification, i.e., whether majority illusion can occur on social networks, and elimination, i.e., how can we eliminate majority illusion by social network rewiring. While we show that the problems we consider are generally NP-complete, we also provide a parameterised complexity analysis, showing FPT-algorithms for the detection problem and W[1]-hardness for the elimination problem, using natural graph-theoretic parameters.

Single-elimination (SE) tournaments are a popular format used in competitive environments and decision making. Algorithms for SE tournament manipulation have been an active topic of research in recent years. 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 obtain both hardness and tractability results. 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.

We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of k robots to their destinations with the aim of minimizing the total energy (i.e., the total length traveled). We develop novel techniques to push beyond previously-established results that were restricted to solid grids. We design a fixed-parameter additive approximation algorithm for this problem parameterized by k alone. This result, which is of independent interest, allows us to prove the following two results pertaining to well-studied coordinated motion planning problems: (1) A fixed-parameter algorithm, parameterized by k, for routing a single robot to its destination while avoiding the other robots, which is related to the famous Rush-Hour Puzzle; and (2) a fixed-parameter algorithm, parameterized by k plus the treewidth of the input graph, for the standard Coordinated Motion Planning (CMP) problem in which we need to route all the k robots to their destinations. The latter of these results implies, among others, the fixed-parameter tractability of CMP parameterized by k on graphs of bounded outerplanarity, which include bounded-height subgrids. We complement the above results with a lower bound which rules out the fixed-parameter tractability for CMP when parameterized by the total energy. This contrasts the recently-obtained tractability of the problem on solid grids under the same parameterization. As our final result, we strengthen the aforementioned fixed-parameter tractability to hold not only on solid grids but all graphs of bounded local treewidth - a class including, among others, all graphs of bounded genus.

In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph is Eulerian. This problem is a natural extension of the Directed Feedback Arc Set problem and is also known to be motivated by certain scenarios arising in the study of housing markets. The complexity of the problem, when parameterized by solution size (i.e., size of the deletion set), has remained unresolved and has been highlighted in several papers. In this work, we answer this question by ruling out (subject to the usual complexity assumptions) a fixed-parameter tractable (FPT) algorithm for this parameter and conduct a broad analysis of the problem with respect to other natural parameterizations. We prove both positive and negative results. Among these, we demonstrate that the problem is also hard (W[1]-hard or even para-NP-hard) when parameterized by either treewidth or maximum degree alone. Complementing our lower bounds, we establish that the problem is in XP when parameterized by treewidth and FPT when parameterized either by both treewidth and maximum degree or by both treewidth and solution size. We show that these algorithms have near-optimal asymptotic dependence on the treewidth assuming the Exponential Time Hypothesis.

The streaming model was introduced to parameterized complexity independently by Fafianie and Kratsch [MFCS14] and by Chitnis, Cormode, Hajiaghayi and Monemizadeh [SODA15]. Subsequently, it was broadened by Chitnis, Cormode, Esfandiari, Hajiaghayi and Monemizadeh [SPAA15] and by Chitnis, Cormode, Esfandiari, Hajiaghayi, McGregor, Monemizadeh and Vorotnikova [SODA16]. Despite its strong motivation, the applicability of the streaming model to central problems in parameterized complexity has remained, for almost a decade, quite limited. Indeed, due to simple Ω(n)-space lower bounds for many of these problems, the kO(1) · polylog(n)-space requirement in the model is too strict.

Abstract. Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received a lot of attention in parameterized complexity. In this paper, we initiate the study of a wide generalization of this problem called the [Formula: see text]-free Strong Connected Component Deletion problem, where [Formula: see text] is a finite family of digraphs. Here, one is given a digraph [Formula: see text] and an integer [Formula: see text], and the objective is to decide whether there is a vertex set of size at most [Formula: see text] whose deletion results in a digraph where every strongly connected component excludes graphs in family [Formula: see text] as (not necessarily induced) subgraphs. When [Formula: see text] comprises only the digraph with a single arc, then this problem is precisely the DFVS problem. Our main result is a proof that this problem is fixed-parameter tractable parameterized by the size of the deletion set if [Formula: see text] only contains rooted graphs or if [Formula: see text] contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the results of Göke, Marx, and Mnich [ Proceedings of the International Conference on Algorithms and Complexity, Springer, 2019, pp. 249–261] 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 that match with the best bounds for DFVS, without using the heavy machinery of shadow removal as is done by Göke, Marx, and Mnich [ Proceedings of the International Conference on Algorithms and Complexity, Springer, 2019, pp. 249–261].

Majority illusion occurs in a social network when the majority of the network vertices belong to a certain type but the majority of each vertex's neighbours belong to a different type, therefore creating the wrong perception, i.e., the illusion, that the majority type is different from the actual one. From a system engineering point of view, this motivates the search for algorithms to detect and, where possible, correct this undesirable phenomenon. In this paper we initiate the computational study of majority illusion in social networks, providing NP-hardness and parametrised complexity results for its occurrence and elimination.

For numerous graph problems in the realm of parameterized algorithms, using the size of a smallest deletion set (called a modulator) into well-understood graph families as parameterization has led to a long and successful line of research. Recently, however, there has been an extensive study of structural parameters that are potentially much smaller than the modulator size. In particular, recent papers [Jansen et al. STOC 2021; Agrawal et al. SODA 2022] have studied parameterization by the size of the modulator to a graph family $\mathcal{H}$ ($\textbf{mod}_{\mathcal{H}}$), elimination distance to $\mathcal{H}$ ($\textbf{ed}_{\mathcal{H}}$), and $\mathcal{H}$-treewidth ($\textbf{tw}_{\mathcal{H}}$). While these new parameters have been successfully exploited to design fast exact algorithms their utility (especially that of latter two) in the context of approximation algorithms is mostly unexplored. The conceptual contribution of this paper is to present novel algorithmic meta-theorems that expand the impact of these structural parameters to the area of FPT Approximation, mirroring their utility in the design of exact FPT algorithms. Precisely, we show that if a covering or packing problem is definable in Monadic Second Order Logic and has a property called Finite Integer Index, then the existence of an FPT Approximation Scheme (FPT-AS, i.e., ($1\pm ε$)-approximation) parameterized these three parameters is in fact equivalent. As concrete exemplifications of our meta-theorems, we obtain FPT-ASes for well-studied graph problems such as Vertex Cover, Feedback Vertex Set, Cycle Packing and Dominating Set, parameterized by these three parameters.

The problem of computing a minimum set of vertices intersecting a finite set of forbidden minors in a given graph is a fundamental graph problem in the area of kernelization with numerous well-studied special cases. A major breakthrough in this line of research was made by Fomin et al. [FOCS 2012], who showed that the ρ-Treewidth Modulator problem (delete minimum number of vertices to ensure that treewidth is at most ρ) has a polynomial kernel of size k^g(ρ) for some function g. A second standout result in this line is that of Giannapoulou et al. [ACM TALG 2017], who obtained an f(η)k^𝒪(1)-size kernel (for some function f) for the η-Treedepth Modulator problem (delete fewest number of vertices to make treedepth at most η) and showed that some dependence of the exponent of k on ρ in the result of Fomin et al. for the ρ-Treewidth Modulator problem is unavoidable under reasonable complexity hypotheses. In this work, we provide an approximate interpolation between these two results by giving, for every ε > 0, a (1+ε)-approximate kernel of size f'(η,ρ,1/ε)⋅ k^g'(ρ) (for some functions f' and g') for the problem of deciding whether k vertices can be deleted from a given graph to obtain a graph that has elimination distance at most η to the class of graphs that have treewidth at most ρ. Graphs of treedepth η are precisely the graphs with elimination distance at most η-1 to the graphs of treewidth 0 and graphs of treewidth ρ are simply graphs with elimination distance 0 to graphs of treewidth ρ. Consequently, our result "approximately" interpolates between these two major results in this active line of research.

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.

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.

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.

In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [ Algorithmica, 75 (2016), pp. 363--382] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most $k$ to any minor-closed class of graphs is fixed-parameter tractable parameterized by $k$ [ Algorithmica, 79 (2017), pp. 139--158]. They showed that graph isomorphism parameterized by the elimination distance to bounded degree graphs is fixed-parameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixed-parameter tractable. Recently, Lindermayr, Siebertz, and Vigny [MFCS 2020, LIPIcs Leibniz Int. Proc. Inform. 170, Wadern Germany, 2020, 65] obtained a fixed-parameter algorithm for this problem in the special case where the input is restricted to $K_5$-minor free graphs. In this paper, we answer the question of Bulian and Dawar in the affirmative for general graphs. In fact, we give a more general result capturing elimination distance to any graph class characterized by a finite set of graphs as forbidden induced subgraphs.

In the Connected ℱ-Deletion problem, ℱ is a fixed finite family of graphs and the objective is to compute a minimum set of vertices (or a vertex set of size at most k for some given k) such that (a) this set induces a connected subgraph of the given graph and (b) deleting this set results in a graph which excludes every F ∈ ℱ as a minor. In the area of kernelization, this problem is well known to exclude a polynomial kernel subject to standard complexity hypotheses even in very special cases such as ℱ = K₂, i.e., Connected Vertex Cover. In this work, we give a (2+ε)-approximate polynomial compression for the Connected ℱ-Deletion problem when ℱ contains at least one planar graph. This is the first approximate polynomial compression result for this generic problem. As a corollary, we obtain the first approximate polynomial compression result for the special case of Connected η-Treewidth Deletion.

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 Directed Feedback Vertex Set, Directed Subset Feedback Vertex Set, Directed Odd Cycle Transversal and Undirected Multicut. 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 Weighted Directed Feedback Vertex Set. 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 cwn(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 Vertex Cover, Component Order Connectivity, Bounded-Degree Vertex Deletion and ℱ-Packing 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 cwn(1)-time bicriteria approximation algorithms for all problems mentioned in the first bullet.

In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most k to any minor-closed class of graphs is fixed-parameter tractable parameterized by k [Algorithmica, 2017]. They showed that Graph Isomorphism parameterized by the elimination distance to bounded degree graphs is fixed-parameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixed-parameter tractable. Recently, Lindermayr et al. [MFCS 2020] obtained a fixed-parameter algorithm for this problem in the special case where the input is restricted to K₅-minor free graphs. In this paper, we answer the question of Bulian and Dawar in the affirmative for general graphs. In fact, we give a more general result capturing elimination distance to any graph class characterized by a finite set of graphs as forbidden induced subgraphs.

Abstract In theDirected Feedback Vertex Set (DFVS)problem, the input is a directed graphDand an integerk. The objective is to determine whether there exists a set of at mostkvertices intersecting every directed cycle ofD. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen et al. (J ACM 55(5):177–186, 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. Since this problem has remained open in spite of the best efforts of a number of prominent researchers and pioneers in the field, a natural step forward is to study the kernelization complexity ofDFVSparameterized by a naturallargerparameter. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlyingundirected 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.

Abstract In this paper we revisit the classical edge disjoint paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our focus lies on structural parameterizations for the problem that allow for efficient (polynomial-time or FPT) algorithms. As our first result, we answer an open question stated in Fleszar et al. (Proceedings of the ESA, 2016), by showing that the problem can be solved in polynomial time if the input graph has a feedback vertex set of size one. We also show that EDP parameterized by the treewidth and the maximum degree of the input graph is fixed-parameter tractable. Having developed two novel algorithms for EDP using structural restrictions on the input graph, we then turn our attention towards the augmented graph, i.e., the graph obtained from the input graph after adding one edge between every terminal pair. In constrast to the input graph, where EDP is known to remain -hard even for treewidth two, a result by Zhou et al. (Algorithmica 26(1):3--30, 2000) shows that EDP can be solved in non-uniform polynomial time if the augmented graph has constant treewidth; we note that the possible improvement of this result to an FPT-algorithm has remained open since then. We show that this is highly unlikely by establishing the [1]-hardness of the problem parameterized by the treewidth (and even feedback vertex set) of the augmented graph. Finally, we develop an FPT-algorithm for EDP by exploiting a novel structural parameter of the augmented graph.

The incidence matrix of a graph is a fundamental object naturally appearing in many applications, involving graphs such as social networks, communication networks, or transportation networks. Often, the data collected about the incidence relations can have some slight noise. In this paper, we initiate the study of the computational complexity of recovering incidence matrices of graphs from a binary matrix: given a binary matrix M which can be written as the superposition of two binary matrices L and S, where S is the incidence matrix of a graph from a specified graph class, and L is a matrix (i) of small rank or, (ii) of small (Hamming) weight. Further, identify all those graphs whose incidence matrices form part of such a superposition. Here, L represents the noise in the input matrix M. Another motivation for this problem comes from the Matroid Minors project of Geelen, Gerards and Whittle, where perturbed graphic and co-graphic matroids play a prominent role. There, it is expected that a perturbed binary matroid (or its dual) is presented as L+S where L is a low rank matrix and S is the incidence matrix of a graph. Here, we address the complexity of constructing such a decomposition. When L is of small rank, we show that the problem is NP-complete, but it can be decided in time (mn)^O(r), where m,n are dimensions of M and r is an upper-bound on the rank of L. When L is of small weight, then the problem is solvable in polynomial time (mn)^O(1). Furthermore, in many applications it is desirable to have the list of all possible solutions for further analysis. We show that our algorithms naturally extend to enumeration algorithms for the above two problems with delay (mn)^O(r) and (mn)^O(1), respectively, between consecutive outputs.

Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance in an effort to define new tractable parameterizations for graph problems and showed that deciding whether a given graph has elimination distance at most k to any minor-closed class of graphs is fixed-parameter tractable parameterized by k [Algorithmica, 2017]. 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. That is, we study the (η,Clq)-Elimination Deletion problem ((η,Clq)-ED Deletion) where, for a fixed η, one is given a graph G and k ∈ ℕ and the objective is to determine whether there is a set S ⊆ V(G) such that the graph G-S has elimination distance at most η to the class of cluster graphs. Our main result is a polynomial kernelization (parameterized by k) for this problem. As components in the proof of our main result, we develop a k^𝒪(η k + η²)n^𝒪(1)-time fixed-parameter algorithm for (η,Clq)-ED Deletion and a polynomial-time factor-min{𝒪(η⋅ opt⋅ log² n),opt^𝒪(1)} approximation algorithm for the same problem.

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].

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 Directed Odd Cycle Transversal (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.

We study the first-order (FO) model checking problem of dense graph classes, namely, those that have FO interpretations in (or are FO transductions of) some sparse graph classes. We give a structural characterization of the graph classes that are FO interpretable in graphs of bounded degree. This characterization allows us to efficiently compute such an FO interpretation for an input graph. As a consequence, we obtain an FPT algorithm for successor-invariant FO model checking on any graph class that is FO interpretable in (or an FO transduction of) a graph class of bounded degree. The approach we use to obtain these results may also be of independent interest.

The Feedback Vertex Set problem is a fundamental computational problem which has been the subject of intensive study in various domains of algorithmics. In this problem, one is given an undirected graph G and an integer k as input. The objective is to determine whether at most k vertices can be deleted from G such that the resulting graph is acyclic. The study of preprocessing algorithms for this problem has a long and rich history, culminating in the quadratic kernelization of Thomasse [SODA 2010]. However, it is known that when the solution is required to induce a connected subgraph (such a set is called a connected feedback vertex set), a polynomial kernelization is unlikely to exist and the problem is NP-hard to approximate below a factor of 2 (assuming the Unique Games Conjecture). In this paper, we show that if one is interested in only preserving approximate solutions (even of quality arbitrarily close to the optimum), then there is a drastic improvement in our ability to preprocess this problem. Specifically, we prove that for every fixed 0 = 1, any c-approximate connected feedback vertex set of G' of size at most k is a c * (1+epsilon)-approximate connected feedback vertex set of G. Our result adds to the set of approximate kernelization algorithms introduced by Lokshtanov et al. [STOC 2017]. As a consequence of our main result, we show that Connected Feedback Vertex Set can be approximated within a factor min{OPT^O(1),n^(1-delta)} in polynomial time for some delta>0.

Single-elimination tournaments are a popular format in competitive environments. The Tournament Fixing Problem (TFP), which is the problem of finding a seeding of the players such that a certain player wins the resulting tournament, is known to be NP-hard in general and fixed-parameter tractable when parameterized by the feedback arc set number of the input tournament (an oriented complete graph) of expected wins/loses. However, the existence of polynomial kernelizations (efficient preprocessing) for TFP has remained open. In this paper, we present the first polynomial kernelization for TFP parameterized by the feedback arc set number of the input tournament. We achieve this by providing a polynomial-time routine that computes a SAT encoding where the number of clauses is bounded polynomially in the feedback arc set number.

In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized by the size of the backdoor. We distinguish between backdoor detection and evaluation of backdoors into the fragments of Horn and Krom formulas. Here we classify the operator fragments of globally-operators for past/future/always, and the combination of them. Detection is shown to be fixed-parameter tractable whereas the complexity of evaluation behaves differently. We show that for Krom formulas the problem is paraNP-complete. For Horn formulas, the complexity is shown to be either fixed parameter tractable or paraNP-complete depending on the considered operator fragment.

We study several problems related to graph modification under connectivity constraints from the perspective of parameterized complexity. In particular, we study (a) (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, and (b) Path-contraction Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while path-contracting k arcs. The parameterized tractability of this last problem was posed in Bang-Jensen and Yeo (2008) [1] as an open question and we answer it here in the negative. On the other hand, we show that preserving (weighted) biconnectivity is fixed-parameter tractable (FPT) and the unweighted case even admits a randomized polynomial kernel. Finally, we show that the most general case of the (unweighted) problem where one would like to preserve ρ-vertex connectivity for any ρ is (non-uniformly) FPT parameterized by k and ρ.

In the classic Integer Programming (IP) problem, the objective is to decide whether, for a given m x n matrix A and an m-vector b=(b_1,..., b_m), there is a non-negative integer n-vector x such that Ax=b. Solving (IP) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. The classic pseudo-polynomial time algorithm of Papadimitriou [J. ACM 1981] for instances of (IP) with a constant number of constraints was only recently improved upon by Eisenbrand and Weismantel [SODA 2018] and Jansen and Rohwedder [ArXiv 2018]. We continue this line of work and show that under the Exponential Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal. We also show that when the matrix A is assumed to be non-negative, a component of Papadimitriou's original algorithm is already nearly optimal under ETH. This motivates us to pick up the line of research initiated by Cunningham and Geelen [IPCO 2007] who studied the complexity of solving (IP) with non-negative matrices in which the number of constraints may be unbounded, but the branch-width of the column-matroid corresponding to the constraint matrix is a constant. We prove a lower bound on the complexity of solving (IP) for such instances and obtain optimal results with respect to a closely related parameter, path-width. Specifically, we prove matching upper and lower bounds for (IP) when the path-width of the corresponding column-matroid is a constant.

In the Directed Feedback Vertex Set (DFVS) problem, we are given as input a directed graph D and an integer k, and the objective is to check whether there exists a set S of at most k vertices such that F=D-S is a directed acyclic graph (DAG). Determining whether DFVS admits a polynomial kernel (parameterized by the solution size) is one of the most important open problems in parameterized complexity. In this article, we give a polynomial kernel for DFVS parameterized by the solution size plus the size of any treewidth-eta modulator, for any positive integer eta. We also give a polynomial kernel for the problem, which we call Vertex Deletion to treewidth-eta DAG, where given as input a directed graph D and a positive integer k, the objective is to decide whether there exists a set of at most k vertices, say S, such that D-S is a DAG and the treewidth of D-S is at most eta.

Given a Counting Monadic Second Order (CMSO) sentence $ψ$, the CMSO$[ψ]$ problem is defined as follows. The input to CMSO$[ψ]$ is a graph $G$, and the objective is to determine whether $G\models ψ$. Our main theorem states that for every CMSO sentence $ψ$, if CMSO$[ψ]$ is solvable in polynomial time on "globally highly connected graphs", then CMSO$[ψ]$ is solvable in polynomial time (on general graphs). We demonstrate the utility of our theorem in the design of parameterized algorithms. Specifically we show that technical problem-specific ingredients of a powerful method for designing parameterized algorithms, recursive understanding, can be replaced by a black-box invocation of our main theorem. We also show that our theorem can be easily deployed to show fixed parameterized tractability of a wide range of problems, where the input is a graph $G$ and the task is to find a connected induced subgraph of $G$ such that "few" vertices in this subgraph have neighbors outside the subgraph, and additionally the subgraph has a CMSO-definable property.

In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruυ for every pair of vertices u, υ ∊ V(G). The objective is to construct a subgraph H of minimum weight which contains ruυ 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 λ-Edge Connected Subgraph (λ-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 λ-Vertex Connected Subgraph (λ-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 2O(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 Minimum Equivalent Graph (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.

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(nk–1m) and the algorithm of Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008] which runs in time O(k!4kk4nm). 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!4kk5(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 Multicut and Directed Subset Feedback Vertex Set.

In the S ubset F eedback V ertex S et (S ubset FVS) problem, the input is a graph G on n vertices and m edges, a subset of vertices T , referred to as terminals, and an integer k . The objective is to determine whether there exists a set of at most k vertices intersecting every cycle that contains a terminal. The study of parameterized algorithms for this generalization of the F eedback V ertex S et problem has received significant attention over the past few years. In fact, the parameterized complexity of this problem was open until 2011, when two groups independently showed that the problem is fixed parameter tractable. Using tools from graph minors,, Kawarabayashi and Kobayashi obtained an algorithm for S ubset FVS running in time O ( f ( k )ċ n 2 m ) [SODA 2012, JCTB 2012]. Independently, Cygan et al. [ICALP 2011, SIDMA 2013] designed an algorithm for S ubset FVS running in time 2 O ( k log k ) ċ n O (1) . More recently, Wahlström obtained the first single exponential time algorithm for S ubset FVS, running in time 4 k ċ n O (1) [SODA 2014]. While the 2 O ( k ) dependence on the parameter k is optimal under the Exponential Time Hypothesis, the dependence of this algorithm as well as those preceding it, on the input size is at least quadratic. In this article, we design the first linear time parameterized algorithms for S ubset FVS. More precisely, we obtain the following new algorithms for S ubset FVS. — A randomized algorithm for S ubset FVS running in time O (25.6 k ċ ( n + m )). — A deterministic algorithm for S ubset FVS running in time 2 O ( k log k ) ċ ( n + m ). Since it is known that assuming the Exponential Time Hypothesis, S ubset FVS cannot have an algorithm running in time 2 o ( k ) n O (1) , our first algorithm obtains the best possible asymptotic dependence on both the parameter as well as the input size. Both of our algorithms are based on “cut centrality,” in the sense that solution vertices are likely to show up in minimum size cuts between vertices sampled from carefully chosen distributions.

Integer Linear Programming (ILP) and its mixed variant (MILP) are archetypical examples of NP-complete optimization problems which have a wide range of applications in various areas of artificial intelligence. However, we still lack a thorough understanding of which structural restrictions make these problems tractable. Here we focus on structure captured via so-called decompositional parameters, which have been highly successful in fields such as boolean satisfiability and constraint satisfaction but have not yet reached their full potential in the ILP setting. In particular, primal treewidth (an established decompositional parameter) can only be algorithmically exploited to solve ILP under restricted circumstances. Our main contribution is the introduction and algorithmic exploitation of two new decompositional parameters for ILP and MILP. The first, torso-width, is specifically tailored to the linear programming setting and is the first decompositional parameter which can also be used for MILP. The latter, incidence treewidth, is a concept which originates from boolean satisfiability but has not yet been used in the ILP setting; here we obtain a full complexity landscape mapping the precise conditions under which incidence treewidth can be used to obtain efficient algorithms. Both of these parameters overcome previous shortcomings of primal treewidth for ILP in unique ways, and consequently push the frontiers of tractability for these important problems.

Single-elimination tournaments (or knockout tournaments) are a popular format in sports competitions that is also widely used for decision making and elections. In this paper we study the algorithmic problem of manipulating the outcome of a tournament. More specifically, we study the problem of finding a seeding of the players such that a certain player wins the resulting tournament. The problem is known to be NP-hard in general. In this paper we present an algorithm for this problem that exploits structural restrictions on the tournament. More specifically, we establish that the problem is fixed-parameter tractable when parameterized by the size of a smallest feedback arc set of the tournament (interpreting the tournament as an oriented complete graph). This is a natural parameter because most problems on tournaments (including this one) are either trivial or easily solvable on acyclic tournaments, leading to the question — what about nearly acyclic tournaments or tournaments with a small feedback arc set? Our result significantly improves upon a recent algorithm by Aziz et al. (2014) whose running time is bounded by an exponential function where the size of a smallest feedback arc set appears in the exponent and the base is the number of players.

The optimization version of the Unique Label Cover problem is at the heart of the Unique Games Conjecture which has played an important role in the proof of several tight inapproximability results. In recent years, this problem has been also studied extensively from the point of view of parameterized complexity. Cygan et al. [FOCS 2012] proved that this problem is fixed-parameter tractable (FPT) and Wahlström [SODA 2014] gave an FPT algorithm with an improved parameter dependence. Subsequently, Iwata, Wahlström and Yoshida [2014] proved that the edge version of Unique Label Cover can be solved in linear FPT-time. That is, there is an FPT algorithm whose dependence on the input-size is linear. However, such an algorithm for the node version of the problem was left as an open problem. In this paper, we resolve this question by presenting the first linear-time FPT algorithm for Node Unique Label Cover.

For a family of graphs F, an n-vertex graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A (multi) graph G = (V, \cup_{i=1}^{\alpha} E_{i}), where the edge set of G is partitioned into \alpha color classes, is called an \alpha-edge-colored graph. A natural extension of the F-Deletion problem to edge-colored graphs is the Simultaneous (F_1, \ldots, F_\alpha)-Deletion problem. In the latter problem, we are given an \alpha-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph G_i - S, where G_i = (V, E_i) and 1 \leq i \leq \alpha, is in F_i. Recently, a subset of the authors considered the aforementioned problem with F_1 = \ldots = F_\alpha being the family of all forests. They showed that the problem is fixed-parameter tractable when parameterized by k and \alpha, and can be solved in O(2^{O(\alpha k)}n^{O(1)}) time. In this work, we initiate the investigation of the complexity of Simultaneous (F_1, \ldots, F_\alpha)-Deletion with different families of graphs. In the process, we obtain a complete characterization of the parameterized complexity of this problem when one or more of the F_i's is the class of bipartite graphs and the rest (if any) are forests. We show that if F_1 is the family of all bipartite graphs and each of F_2 = F_3 = \ldots = F_\alpha is the family of all forests then the problem is fixed-parameter tractable parameterized by k and \alpha. However, even when F_1 and F_2 are both the family of all bipartite graphs, then the Simultaneous (F_1, F_2)-Deletion} problem itself is already W[1]-hard.

We consider the problem of firefighting to save a critical subset of nodes. The firefighting game is a turn-based game played on a graph, where the fire spreads to vertices in a breadth-first manner from a source, and firefighters can be placed on yet unburnt vertices on alternate rounds to block the fire. In this work, we consider the problem of saving a critical subset of nodes from catching fire, given a total budget on the number of firefighters. We show that the problem is para-NP-hard when parameterized by the size of the critical set. We also show that it is fixed-parameter tractable on general graphs when parameterized by the number of firefighters. We also demonstrate improved running times on trees and establish that the problem is unlikely to admit a polynomial kernelization (even when restricted to trees). Our work is the first to exploit the connection between the firefighting problem and the notions of important separators and tight separator sequences. Finally, we consider the spreading model of the firefighting game, a closely related problem, and show that the problem of saving a critical set parameterized by the number of firefighters is W[2]-hard, which contrasts our FPT result for the non-spreading model.

In this paper we revisit the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our focus lies on structural parameterizations for the problem that allow for efficient (polynomial-time or fpt) algorithms. As our first result, we answer an open question stated in Fleszar, Mnich, and Spoerhase (2016), by showing that the problem can be solved in polynomial time if the input graph has a feedback vertex set of size one. We also show that EDP parameterized by the treewidth and the maximum degree of the input graph is fixed-parameter tractable. Having developed two novel algorithms for EDP using structural restrictions on the input graph, we then turn our attention towards the augmented graph, i.e., the graph obtained from the input graph after adding one edge between every terminal pair. In constrast to the input graph, where EDP is known to remain NP-hard even for treewidth two, a result by Zhou et al. (2000) shows that EDP can be solved in non-uniform polynomial time if the augmented graph has constant treewidth; we note that the possible improvement of this result to an fpt-algorithm has remained open since then. We show that this is highly unlikely by establishing the W[1]-hardness of the problem parameterized by the treewidth (and even feedback vertex set) of the augmented graph. Finally, we develop an fpt-algorithm for EDP by exploiting a novel structural parameter of the augmented graph.

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.

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)}.

We show that CSP is fixed-parameter tractable when parameterized by the treewidth of a backdoor into any tractable CSP problem over a finite constraint language. This result combines the two prominent approaches for achieving tractability for CSP: (i) structural restrictions on the interaction between the variables and the constraints and (ii) language restrictions on the relations that can be used inside the constraints. Apart from defining the notion of backdoor-treewidth and showing how backdoors of small treewidth can be used to efficiently solve CSP, our main technical contribution is a fixed-parameter algorithm that finds a backdoor of small treewidth.

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′ ≤ kO(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).

The notion of resolving sets in a graph was introduced by Slater [Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Util. Math., Winnipeg, 1975, pp. 549--559] and Harary and Melter [Ars Combin., 2 (1976), pp. 191--195] as a way of uniquely identifying every vertex in a graph. A set of vertices in a graph is a resolving set if for any pair of vertices $x$ and $y$ there is a vertex in the set which has distinct distances to $x$ and $y$. A smallest resolving set in a graph is called a metric basis and its size, the metric dimension of the graph. The problem of computing the metric dimension of a graph is a well-known NP-hard problem and while it was known to be polynomial time solvable on trees, it is only recently that efforts have been made to understand its computational complexity on various restricted graph classes. In recent work, Foucaud [Algorithmica, 2016, pp. 1--31] showed that this problem is NP-complete even on interval graphs. They complemented this result by also showing that it is fixed-parameter tractable (FPT) parameterized by the metric dimension of the graph. In this work, we show that this FPT result can in fact be extended to all graphs of bounded tree-length. This includes well-known classes like chordal graphs, AT-free graphs, and permutation graphs. We also show that this problem is FPT parameterized by the modular-width of the input graph.

We study the parameterized complexity of the directed variant of the classical Steiner Tree problem on various classes of directed sparse graphs. While the parameterized complexity of Steiner Tree parameterized by the number of terminals is well understood, not much is known about the parameterization by the number of nonterminals in the solution tree. All that is known for this parameterization is that both the directed and the undirected versions are W[2]-hard on general graphs and hence unlikely to be fixed parameter tractable (FPT). The undirected Steiner Tree problem becomes FPT when restricted to sparse classes of graphs such as planar graphs, but the techniques used to show this result break down on directed planar graphs. In this article we precisely chart the tractability border for Directed Steiner Tree (DST) on sparse graphs parameterized by the number of nonterminals in the solution tree. Specifically, we show that the problem is FPT on graphs excluding a topological minor but becomes W[2]-hard on graphs of degeneracy 2. On the other hand we show that if the subgraph induced by the terminals is acyclic, then the problem becomes FPT on graphs of bounded degeneracy. We further show that our algorithm achieves the best possible asymptotic running time dependence on the solution size and degeneracy of the input graph, under standard complexity theoretic assumptions. Using the ideas developed for DST, we also obtain improved algorithms for Dominating Set on sparse undirected graphs. These algorithms are asymptotically optimal. (An erratum is attached.)

In the Subset Odd Cycle Transversal (Subset OCT) problem, the input is a graph $G$, a subset of vertices $T$ and a positive integer $k$ and the objective is to determine whether there exists a $k$-sized vertex subset that intersects every odd cycle containing a vertex from $T$. Clearly, Subset OCT is a generalization of the classic Odd Cycle Transversal problem where the objective is to determine whether there exists a $k$-sized vertex subset that intersects every odd cycle in the given graph. We remark that Subset OCT also generalizes the well known Multiway Cut problem, as well as a parity constrained variant, the Odd Multiway Cut problem. Recently, Kakimura, Kawarabayashi, and Kobayashi [ Proceedings of SODA, 2012, pp. 1726--1736] proposed a fixed parameter tractable (FPT) algorithm for this problem that runs in time $f(k)mn^3$ using the theory of graph minors, where $f$ is some function, and $n$ and $m$ denote the number of vertices and edges in the graph. However, the dependence of this function on $k$ is at least triple exponential. In this paper, we give the first FPT algorithm for this problem where the exponential dependence of the running time of the algorithm on $k$ is polynomial. Our algorithm avoids the use of the theory of graph minors, is self contained, and runs in time $2^{\mathcal{O}(k^3\log k)}mn^2\log^2 n$, thus improving upon the algorithm of Kakimura and co-authors with respect to both the parameter as well as the input size. Our algorithm utilizes a recursive application of “generalized” important separators to reduce the subset version of this problem to the standard version of the problem.

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 article 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 is not 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, that is, 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 O (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 is not 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.

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 and later by Goldberg and Karzanov. In this article, we introduce a separation problem, d -S kew -S ymmetric M ulticut , where we are given a skew-symmetric graph D , a family τ of d -size subsets of vertices, and an integer k . The objective is to decide whether there is a set X ⊑ A of k arcs such that every set J in the family has a vertex υ such that υ and σ(υ) are in different strongly connected components of D ′=( V ,A \ ( X ∪ σ( X )). In this work, we give an algorithm for d -S kew -S ymmetric M ulticut that runs in time O ((4 d ) k ( m + n +ℓ)), where m is the number of arcs in the graph, n is the number of vertices, and ℓ is the length of the family given in the input. This problem, apart from being independently interesting, also captures the main combinatorial difficulty of 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 that runs in time O (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 that run in time O (4 k k 4 ( m + n )) and O (4 k k 5 ( m + n )), respectively, where k is the size of the solution, and m and n are the number of edges and vertices respectively. This resolves an open problem posed by Reed et al. and improves on the earlier almost-linear-time algorithm of Kawarabayashi and Reed. — 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 D eletion q-Horn B ackdoor S et D etection that runs in time O (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 work by Narayanaswamy et al. Using this result, we get an algorithm for S atisfiability that runs in time O (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.

The purpose of this article is two fold: (a) to formally introduce a stronger version of graph deletion problems; and (b) to study this version in the context of bipartite graphs. Given a family of graphs F, a typical instance of parameterized graph deletion problem consists of an undirected graph G and a positive integer k and the objective is to check whether we can delete at most k vertices (or k edges) such that the resulting graph belongs to F. Another version that has been recently studied is the one where the input contains two integers k and l and the objective is to check whether we can delete at most k vertices and l edges such that the resulting graph belongs to F. In this paper, we propose and initiate the study of a more general version which we call strong deletion. In this problem, given an undirected graph G and positive integers k and l, the objective is to check whether there exists a vertex subset S of size at most k such that each connected component of G-S can be transformed into a graph in F by deleting at most l edges. In this paper we study this stronger version of deletion problems for the class of bipartite graphs. In particular, we study Strong Bipartite Deletion, where given an undirected graph G and positive integers k and l, the objective is to check whether there exists a vertex subset S of size at most k such that each connected component of G-S can be made bipartite by deleting at most l edges. While fixed-parameter tractability when parameterizing by k or l alone is unlikely, we show that this problem is fixed-parameter tractable (FPT) when parameterized by both k and l.

In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized by the size of the backdoor. We distinguish between backdoor detection and evaluation of backdoors into the fragments of Horn and Krom formulas. Here we classify the operator fragments of globally-operators for past/future/always, and the combination of them. Detection is shown to be fixed-parameter tractable (FPT) whereas the complexity of evaluation behaves differently. We show that for Krom formulas the problem is paraNP-complete. For Horn formulas, the complexity is shown to be either fixed parameter tractable or paraNP-complete depending on the considered operator fragment.

We study the FO model checking problem of dense graph classes, namely those which are FO-interpretable in some sparse graph classes. Note that if an input dense graph is given together with the corresponding FO interpretation in a sparse graph, one can easily solve the model checking problem using the existing algorithms for sparse graph classes. However, if the assumed interpretation is not given, then the situation is markedly harder.

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.

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.

An instance of the $(n-k)$-Set Cover or the $(n-k)$-Test Cover problems is of the form $(\mathcal{U},\mathcal{S},k)$, where $\mathcal{U}$ is a set with $n$ elements, $\mathcal{S}\subseteq 2^\mathcal{U}$ with $|\mathcal{S}|=m$, and $k$ is the parameter. The instance is a Yes-instance of $(n-k)$-Set Cover if and only if there exists $\mathcal{S}'\subseteq\mathcal{S}$ with $|\mathcal{S}'|\leq n-k$ such that every element of $\mathcal{U}$ is contained in some set in $\mathcal{S}'$. Similarly, it is a Yes-instance of $(n-k)$-Test Cover if and only if there exists $\mathcal{S}'\subseteq\mathcal{S}$ with $|\mathcal{S}'|\leq n-k$ such that for any pair of elements from $\mathcal{U}$, there exists a set in $\mathcal{S}'$ that contains one of them but not the other. It is known in the literature that both $(n-k)$-Set Cover and $(n-k)$-Test Cover do not admit polynomial kernels (under some well-known complexity theoretic assumptions). However, in this paper we show that they do admit “partially polynomial kernels”: we give polynomial time algorithms that take as input an instance $(\mathcal{U},\mathcal{S},k)$ of $(n-k)$-Set Cover (respectively, $(n-k)$-Test Cover) and return an equivalent instance $(\tilde{\mathcal{U}},\tilde{\mathcal{S}}, \tilde{k})$ of $(n-k)$-Set Cover (respectively, $(n-k)$-Test Cover) with $\tilde{k} \leq k$ and $| \tilde{\mathcal{U}}|= \mathcal{O}(k^2)$ (respectively, $|\tilde{\mathcal{U}}|=\mathcal{O}(k^7)$). These results allow us to generalize, improve, and unify several results known in the literature. For example, these immediately imply traditional kernels when input instances satisfy certain “sparsity properties.” Using a part of our partial kernelization algorithm for $(n-k)$-Set Cover, we also get an improved fixed-parameter tractable algorithm for this problem which runs in time $\mathcal{O}(4^kk^{\mathcal{O}(1)}(m+n)+mn)$ improving over the previous best of $\mathcal{O}(8^{k+o(k)}(m+n)^{\mathcal{O}(1)})$. On the other hand, the partially polynomial kernel for $(n-k)$-Test Cover gives an algorithm with running time $\mathcal{O}(2^{\mathcal{O}(k^2)}(m+n)^{\mathcal{O}(1)})$. We believe such an approach could also be useful for other covering problems.

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) · n2.

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 log2 n)-time procedure of Fomin et al. (FOCS 2012). The new deterministic linear time protrusion replacer has several applications in kernelization and parameterized algorithms.

Given a graph G and a function f:V(G) -> [V(G)], 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. Tutte (1954) showed that one can check whether a given graph has a specified f-factor in polynomial time. However, detecting a connected f-factor is NP-complete, even when f is a constant function - a foremost example is the problem of checking whether a graph has a Hamiltonian cycle; here f is a function which maps every vertex to 2. The current best algorithm for this latter problem is due to Björklund (FOCS 2010), and runs in randomized O^*(1.657^n) time (the O^*() notation hides polynomial factors). This was the first superpolynomial improvement, in nearly fifty years, over the previous best algorithm of Bellman, Held and Karp (1962) which checks for a Hamiltonian cycle in deterministic O(2^n*n^2) time. In this paper we present the first vertex-exponential algorithms for the more general problem of finding a connected f-factor. Our first result is a randomized algorithm which, given a graph G on n vertices and a function f:V(G) -> [n], checks whether G has a connected f-factor in O^*(2^n) time. We then extend our result to the case when f is a mapping from V(G) to {0,1} and the degree of every vertex v in the subgraph H is required to be f(v)(mod 2). This generalizes the problem of checking whether a graph has an Eulerian subgraph; this is a connected subgraph whose degrees are all even (f(v) equiv 0). Furthermore, we show that the min-cost editing and edge-weighted versions of these problems can be solved in randomized O^*(2^n) time as long as the costs/weights are bounded polynomially in n.

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-Skew-Symmetric Multicut, 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-Skew-Symmetric Multicut which runs in time ((4d)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-Skew-Symmetric Multicut 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 Almost 2-SAT is a special case of 1-Skew-Symmetric Multicut, resulting in an algorithm for Almost 2-SAT which runs in time (4kk4ℓ) where k is the size of the solution and ℓ is the length of the input formula. Then, using linear time parameter preserving reductions to Almost 2-SAT, we obtain algorithms for Odd Cycle Transversal and Edge Bipartization which run in time (4kk4(m+n)) and (4kk5(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 Deletion q-Horn Backdoor Set Detection is a special case of 3-Skew-Symmetric Multicut, giving us an algorithm for Deletion q-Horn Backdoor Set Detection which runs in time (12kk5ℓ) 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 Satisfiability which runs in time (12kk5ℓ) where k is the size of the smallest q-Horn deletion backdoor set, with ℓ being the length of the input formula.

We investigate the parameterized complexity of Vertex Cover parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that combining previously known preprocessing rules with the most straightforward branching algorithm yields an O *(2.618 k ) algorithm for the problem. Here, k is the excess of the vertex cover size over the LP optimum, and we write O *( f ( k )) for a time complexity of the form O ( f ( k ) n O (1) ). We proceed to show that a more sophisticated branching algorithm achieves a running time of O *(2.3146 k ). Following this, using previously known as well as new reductions, we give O *(2.3146 k ) algorithms for the parameterized versions of Above Guarantee Vertex Cover , Odd Cycle Transversal , Split Vertex Deletion, and Almost 2-SAT , and O *(1.5214 k ) algorithms for König Vertex Deletion and Vertex Cover parameterized by the size of the smallest odd cycle transversal and König vertex deletion set. These algorithms significantly improve the best known bounds for these problems. The most notable improvement among these is the new bound for Odd Cycle Transversal —this is the first algorithm that improves on the dependence on k of the seminal O *(3 k ) algorithm of Reed, Smith, and Vetta. Finally, using our algorithm, we obtain a kernel for the standard parameterization of Vertex Cover with at most 2 k − c log k vertices. Our kernel is simpler than previously known kernels achieving the same size bound.

In a typical covering problem we are given a universe U of size n, a family S (S could be given implicitly) of size m and an integer k and the objective is to check whether there exists a subfamily S' \subseteq S of size at most k satisfying some desired properties. If S' is required to contain all the elements of U then it corresponds to the classical Set Cover problem. On the other hand if we require S' to satisfy the property that for every pair of elements x,y \in U there exists a set S \in S' such that |S \cap {x,y}|=1 then it corresponds to the Test Cover problem. In this paper we consider a natural parameterization of Set Cover and Test Cover. More precisely, we study the (n-k)-Set Cover and (n-k)-Test Cover problems, where the objective is to find a subfamily S' of size at most n-k satisfying the respective properties, from the kernelization perspective. It is known in the literature that both (n-k)-Set Cover and (n-k)-Test Cover do not admit polynomial kernels (under some well known complexity theoretic assumptions). However, in this paper we show that they do admit "partially polynomial kernels". More precisely, we give polynomial time algorithms that take as input an instance (U,S,k) of (n-k)-Set Cover (n-k)-Test Cover) and return an equivalent instance (~U,~S,~k) of (n-k)-Set Cover (respectively (n-k)-Test Cover) with ~k <= k and |~U|= O(k^2) (|~U|=O(k^7)). These results allow us to generalize, improve and unify several results known in the literature. For example, these immediately imply traditional kernels when input instances satisfy certain "sparsity properties". Using a part of our kernelization algorithm for (n-k)-Set Cover, we also get an improved FPT algorithm for this problem which runs in time O(4^k*k^{\O(1)}*(m+n)) improving over the previous best of O(8^{k+o(k)}*(m+n)^{O(1)}). On the other hand the partially polynomial kernel for (n-k)-Test Cover implies the first single exponential FPT algorithm, an algorithm with running time O(2^{O(k^2)}*(m+n)^{O(1)}). We believe such an approach will also be useful for other covering problems as well.

The class q-Horn, introduced by Boros, Crama and Hammer in 1990, is one of the largest known classes of propositional CNF formulas for which satisfiability can be decided in polynomial time. This class properly contains the fundamental classes of Horn and Krom formulas as well as the class of renamable (or disguised) Horn formulas. In this paper we extend this class so that its favorable algorithmic properties can be made accessible to formulas that are outside but "close"' to this class. We show that deciding satisfiability is fixed-parameter tractable parameterized by the distance of the given formula from q-Horn. The distance is measured by the smallest number of variables that we need to delete from the formula in order to get a q-Horn formula, i.e., the size of a smallest deletion backdoor set into the class q-Horn. This result generalizes known fixed-parameter tractability results for satisfiability decision with respect to the parameters distance from Horn, Krom, and renamable Horn.

We investigate the parameterized complexity of Vertex Cover parameterized above the optimum value of the linear programming (LP) relaxation of the integer linear programming formulation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that even the most straightforward branching algorithm (after some preprocessing) results in an O^*(2.6181^r) algorithm for the problem where r is the excess of the vertex cover size over the LP optimum. We write O^*(f(k)) for a time complexity of the form O(f(k)n^{O(1)}), where f(k) grows exponentially with k. Then, using known and new reductions, we give O^*(2.6181^k) algorithms for the parameterized versions of Above Guarantee Vertex Cover, Odd Cycle Transversal, Split Vertex Deletion and Almost 2-SAT, and an O^*(1.6181^k) algorithm for Konig Vertex Deletion, Vertex Cover Param by OCT and Vertex Cover Param by KVD. These algorithms significantly improve the best known bounds for these problems. The notable improvement is the bound for Odd Cycle Transversal for which this is the first major improvement after the first algorithm that showed it fixed-parameter tractable in 2003. We also observe that using our algorithm, one can obtain a simple kernel for the classical vertex cover problem with at most 2k-O(log k) vertices.