We present a linear-time algorithm to compute a decomposition scheme for graphs G that have a set X ⊆ V ( G ), called a treewidth-modulator , such that the treewidth of G − X is bounded by a constant. Our decomposition, called a protrusion decomposition , is the cornerstone in obtaining the following two main results. Our first result is that any parameterized graph problem (with parameter k ) that has a finite integer index and such that Y es -instances have a treewidth-modulator of size O ( k ) admits a linear kernel on the class of H -topological-minor-free graphs, for any fixed graph H . This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus and H -minor-free graphs. Let F be a fixed finite family of graphs containing at least one planar graph. Given an n -vertex graph G and a non-negative integer k , P lanar - F -D eletion asks whether G has a set X ⊆ V ( G ) such that | X | ⩽ k and G − X is H -minor-free for every H ϵ F . As our second application, we present the first single-exponential algorithm to solve P lanar - F -D eletion . Namely, our algorithm runs in time 2 O ( k ) · n 2 , which is asymptotically optimal with respect to k . So far, single-exponential algorithms were only known for special cases of the family F .

We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NP-hard, none of the problems can be solved in subexponential time unless the exponential time hypothesis fails. Misra, Panolan, and Saurabh (MFCS 2013) argue that introducing a bound on the number of connected components in the solution should not make the problem easier: In particular, they argue that the subexponential time algorithm for editing to a fixed number of clusters (p-Cluster Editing) by Fomin et al. (J. Comput. Syst. Sci., 80(7) 2014) is an exception rather than the rule. Here, p is a secondary parameter, bounding the number of components in the solution. However, upon bounding the number of stars or bicliques in the solution, we obtain algorithms which run in time O(2^{3*sqrt(pk)} + n + m) for p-Starforest Editing and O(2^{O(p * sqrt(k) * log(pk))} + n + m) for p-Bicluster Editing. We obtain a similar result for the more general case of t-Partite p-Cluster Editing. This is subexponential in k for a fixed number of clusters, since p is then considered a constant. Our results even out the number of multivariate subexponential time algorithms and give reasons to believe that this area warrants further study.

A fundamental theorem of Courcelle states that every problem definable in Monadic Second-Order Logic (MSO) is solvable in linear time on graphs of bounded treewidth.In this paper, we report on our ongoing effort to develop a general purpose software tool designed to solve MSO-definable optimization and decision problems on graphs of small treewidth.We discuss the theoretical underpinnings of our tool and present experimental results, which indicate that for some natural optimization problems MSO based approaches might be a suitable alternative to ILP solvers.

One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quantifications (MSO2) is decidable in linear time on any class of graphs of bounded tree-width. In the parlance of parameterized complexity, this means that MSO2 model-checking is fixed-parameter tractable with respect to the tree-width as parameter. Recently, Kreutzer and Tazari proved a corresponding complexity lower-bound---that MSO2 model-checking is not even in XP wrt the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. Of course, this is not an unconditional result but holds modulo a certain complexity-theoretic assumption, namely, the Exponential Time Hypothesis (ETH). In this paper we present a closely related result. We show that even MSO1 model-checking with a fixed set of vertex labels, but without edge-set quantifications, is not in XP wrt the formula size as parameter for graph classes which are subgraph-closed and whose tree-width is poly-logarithmically unbounded unless the non-uniform ETH fails. In comparison to Kreutzer and Tazari, (1) we use a stronger prerequisite, namely non-uniform instead of uniform ETH, to avoid the effectiveness assumption and the construction of certain obstructions used in their proofs; and (2) we assume a different set of problems to be efficiently decidable, namely MSO1-definable properties on vertex labeled graphs instead of MSO2-definable properties on unlabeled graphs. Our result has an interesting consequence in the realm of digraph width measures: Strengthening a recent result, we show that no subdigraph-monotone measure can be algorithmically useful, unless it is within a poly-logarithmic factor of (undirected) tree-width.

We show that for every fixed j ≥ i ≥ 1, the k -D ominating S et problem restricted to graphs that do not have K ij (the complete bipartite graph on ( i + j ) vertices, where the two parts have i and j vertices, respectively) as a subgraph is fixed parameter tractable (FPT) and has a polynomial kernel. We describe a polynomial-time algorithm that, given a K i,j -free graph G and a nonnegative integer k , constructs a graph H (the “kernel”) and an integer k ' such that (1) G has a dominating set of size at most k if and only if H has a dominating set of size at most k ', (2) H has O (( j + 1) i + 1 k i 2 ) vertices, and (3) k ' = O (( j + 1) i + 1 k i 2 ). Since d -degenerate graphs do not have K d+1,d+1 as a subgraph, this immediately yields a polynomial kernel on O (( d + 2) d +2 k ( d + 1) 2 ) vertices for the k -D ominating S et problem on d -degenerate graphs, solving an open problem posed by Alon and Gutner [Alon and Gutner 2008; Gutner 2009]. The most general class of graphs for which a polynomial kernel was previously known for k -D ominating S et is the class of K h -topological-minor-free graphs [Gutner 2009]. Graphs of bounded degeneracy are the most general class of graphs for which an FPT algorithm was previously known for this problem. K h -topological-minor-free graphs are K i,j -free for suitable values of i,j (but not vice-versa), and so our results show that k -D ominating S et has both FPT algorithms and polynomial kernels in strictly more general classes of graphs. Using the same techniques, we also obtain an O ( jk i ) vertex-kernel for the k -I ndependent D ominating S et problem on K i,j -free graphs.