We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time $$\mathcal {O}(2^{\lambda n})$$ for some $$\lambda <1$$ . These are the first algorithms breaking the trivial $$2^n n^{\mathcal {O}(1)}$$ bound of the brute-force search for these problems.

We obtain an algorithmic metatheorem for the following optimization problem. Let $\varphi$ be a counting monadic second order logic (CMSO) formula and $t\geq 0$ be an integer. For a given graph $G=(V,E)$, the task is to maximize $|X|$ subject to the following: there is a set $ F\subseteq V$ such that $X\subseteq F $, the subgraph $G[F]$ induced by $F$ is of treewidth at most $t$, and the structure $(G[F],X)$ models $\varphi$, i.e., $(G[F],X)\models\varphi$. We give an algorithm solving this optimization problem on any $n$-vertex graph $G$ in time ${\cal O}(|\Pi_G| \cdot n^{t+4}\cdot f(t,\varphi))$, where $\Pi_G$ is the set of all potential maximal cliques in $G$ and $f$ is a function of $t$ and $\varphi$ only. Pipelined with the known bounds on the number of potential maximal cliques in different graph classes, there are a plethora of algorithmic consequences extending and subsuming many known results on polynomial-time algorithms for graph classes. We also show that all potential maximal cliques of $G$ can be enumerated in time ${\cal O}(1.7347^n)$. This implies the existence of an exact exponential algorithm of running time ${\cal O}(1.7347^n)$ for many NP-hard problems related to finding maximum induced subgraphs with different properties.

We obtain an algorithmic meta-theorem for the following optimization problem. Let φ be a Counting Monadic Second Order Logic (CMSO) formula and t ≥ 0 be an integer. For a given graph G = (V, E), the task is to maximize |X| subject to the following: there is a set F ⊆ V such that X ⊆ F, the subgraph G[F] induced by F is of treewidth at most t, and structure (G[F], X) models φ, i.e. (G[F], X) ⊨ φ. Special cases of this optimization problem are the following generic examples. Each of these special cases contains various problems as a special subcase: Maximum Induced Subgraph with ≤ ℓ copies of ℱm-cycles, where for fixed nonnegative integers m and ℓ, the task is to find a maximum induced subgraph of a given graph with at most ℓ vertex-disjoint cycles of length 0 (mod m). For example, this encompasses the problems of finding a maximum induced forest or a maximum subgraph without even cycles. Minimum ℱ-Deletion, where for a fixed finite set of graphs ℱ containing a planar graph, the task is to find a maximum induced subgraph of a given graph containing no graph from ℱ as a minor. Examples of Minimum ℱ-Deletion are the problems of finding a minimum vertex cover or a minimum number of vertices required to delete from the graph to obtain an outerplanar graph. Independent ℋ-packing, where for a fixed finite set of connected graphs ℋ, the task is to find an induced subgraph F of a given graph with the maximum number of connected components, such that each connected component of F is isomorphic to some graph from ℋ. For example, the problem of finding a maximum induced matching or packing into nonadjacent triangles, are the special cases of this problem. We give an algorithm solving the optimization problem on an n-vertex graph G in time (|ΠG| · nt+4 · f(t, φ)), where ΠG is the set of all potential maximal cliques in G and f is a function of t and φ only. We also show how similar running time can be obtained for the weighted version of the problem. Pipelined with known bounds on the number of potential maximal cliques, we derive a plethora of algorithmic consequences extending and subsuming many known results on algorithms for special graph classes and exact exponential algorithms.

The Independent Set problem is NP-hard in general, however polynomial time algorithms exist for the problem on various specific graph classes. Over the last couple of decades there has been a long sequence of papers exploring the boundary between the NP-hard and polynomial time solvable cases. In particular the complexity of Independent Set on P5-free graphs has received significant attention, and there has been a long list of results showing that the problem becomes polynomial time solvable on sub-classes of P5-free graphs. In this paper we give the first polynomial time algorithm for Independent Set on P5-free graphs. Our algorithm also works for the Weighted Independent Set problem.

Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a graph from F as an induced subgraph. It appeared recently that special cases of F-Completion, the problem of completing into a chordal graph known as "Minimum Fill-in", corresponding to the case of F={C_4,C_5,C_6,...}, and the problem of completing into a split graph, i.e., the case of F={C_4,2K_2,C_5}, are solvable in parameterized subexponential time. The exploration of this phenomenon is the main motivation for our research on F-Completion. In this paper we prove that completions into several well studied classes of graphs without long induced cycles also admit parameterized subexponential time algorithms by showing that: - The problem Trivially Perfect Completion is solvable in parameterized subexponential time, that is F-Completion for F={C_4,P_4}, a cycle and a path on four vertices. - The problems known in the literature as Pseudosplit Completion, the case where F={2K_2,C_4}, and Threshold Completion, where F={2K_2,P_4,C_4}, are also solvable in subexponential time. We complement our algorithms for $F$-Completion with the following lower bounds: - For F={2K_2}, F={C_4}, F={P_4}, and F={2K_2,P_4}, F-Completion cannot be solved in time 2^o(k).n^O(1) unless the Exponential Time Hypothesis (ETH) fails. Our upper and lower bounds provide a complete picture of the subexponential parameterized complexity of F-Completion problems for F contained inside {2K_2,C_4,P_4}.

Given a source string u and a target string w, to decide whether w can be obtained by applying a string morphism on u (i. e., uniformly replacing the symbols in u by strings) constitutes an NP-complete problem. For example, the target string w := baaba can be obtained from the source string u := aba, by replacing a and b in u by the strings ba and a, respectively. In this paper, we contribute to the recently started investigation of the computational complexity of the string morphism problem by studying it in the framework of parameterised complexity.

In the Correlation Clustering problem, also known as Cluster Editing, we are given an undirected graph G and a positive integer k; the task is to decide whether G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, that is, by adding or deleting at most k edges. The motivation of the problem stems from various tasks in computational biology (Ben-Dor et al., Journal of Computational Biology 1999) and machine learning (Bansal et al., Machine Learning 2004). Although in general Correlation Clustering is APX-hard (Charikar et al., FOCS 2003), the version of the problem where the number of cliques may not exceed a prescribed constant p admits a PTAS (Giotis and Guruswami, SODA 2006). We study the parameterized complexity of Correlation Clustering with this restriction on the number of cliques to be created. We give an algorithm that - in time O(2^{O(sqrt{pk})} + n+m) decides whether a graph G on n vertices and m edges can be transformed into a cluster graph with exactly p cliques by changing at most k adjacencies. We complement these algorithmic findings by the following, surprisingly tight lower bound on the asymptotic behavior of our algorithm. We show that unless the Exponential Time Hypothesis (ETH) fails - for any constant 0 <= sigma <= 1, there is p = Theta(k^sigma) such that there is no algorithm deciding in time 2^{o(sqrt{pk})} n^{O(1)} whether an n-vertex graph G can be transformed into a cluster graph with at most p cliques by changing at most k adjacencies. Thus, our upper and lower bounds provide an asymptotically tight analysis of the multivariate parameterized complexity of the problem for the whole range of values of p from constant to a linear function of k.

Minimum Fill-in is a fundamental and classical problem arising in sparse matrix computations. In terms of graphs it can be formulated as a problem of finding a triangulation of a given graph with the minimum number of edges. By the classical result of Rose, Tarjan, Lueker, and Ohtsuki from 1976, an inclusion minimal triangulation of a graph can be found in polynomial time but, as it was shown by Yannakakis in 1981, finding a triangulation with the minimum number of edges is NP-hard. In this paper, we study the parameterized complexity of local search for the Minimum Fill-in problem in the following form: Given a triangulation H of a graph G, is there a better triangulation, i.e. triangulation with less edges than H, within a given distance from H? We prove that this problem is fixed-parameter tractable (FPT) being parameterized by the distance from the initial triangulation by providing an algorithm that in time O(f(k) |G|^{O(1)}) decides if a better triangulation of G can be obtained by swapping at most k edges of H. Our result adds Minimum Fill-in to the list of very few problems for which local search is known to be FPT.

The Minimum Fill-in problem is used to decide if a graph can be triangulated by adding at most $k$ edges. In 1994, Kaplan, Shamir, and Tarjan showed that the problem is solvable in time $\mathcal{O}(2^{\mathcal{O}({k})}+k^2 nm)$ on graphs with $n$ vertices and $m$ edges and thus is fixed parameter tractable. Here, we give the first subexponential parameterized algorithm solving Minimum Fill-in in time $\mathcal{O}(2^{\mathcal{O}(\sqrt{k}\log{k})} +k^2 nm)$. This substantially lowers the complexity of the problem. Techniques developed for Minimum Fill-in can be used to obtain subexponential parameterized algorithms for several related problems, including Minimum Chain Completion, Chordal Graph Sandwich, and Triangulating Colored Graph.

It is known that the problem of deleting at most $k$ vertices to obtain a proper interval graph (Proper Interval Vertex Deletion) is fixed parameter tractable. However, whether the problem admits a polynomial kernel or not was open. Here, we answer this question in the affirmative by obtaining a polynomial kernel for Proper Interval Vertex Deletion. This resolves an open question of van Bevern et al. [Graph-Theoretic Concepts in Computer Science (WG 2010), Lecture Notes in Comput. Sci. 6410, Springer, Berlin, 2010, pp. 232--243].

The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. Kaplan, Shamir, and Tarjan [FOCS 1994] have shown that the problem is solvable in time on graphs with n vertices and m edges and thus is fixed parameter tractable. Here, we give the first subexponential parameterized algorithm solving Minimum Fill-in in time . This substantially lowers the complexity of the problem. Techniques developed for Minimum Fill-in can be used to obtain subexponential parameterized algorithms for several related problems including Minimum Chain Completion, Chordal Graph Sandwich, and Triangulating Colored Graph.

The k -Leaf Out-Branching problem is to find an out-branching, that is a rooted oriented spanning tree, with at least k leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the k -Leaf-Out-Branching problem. We give the first polynomial kernel for Rooted k -Leaf-Out-Branching, a variant of k -Leaf-Out-Branching where the root of the tree searched for is also a part of the input. Our kernel with O ( k 3 ) vertices is obtained using extremal combinatorics. For the k -Leaf-Out-Branching problem, we show that no polynomial-sized kernel is possible unless coNP is in NP/poly . However, our positive results for Rooted k -Leaf-Out-Branching immediately imply that the seemingly intractable k -Leaf-Out-Branching problem admits a data reduction to n independent polynomial-sized kernels. These two results, tractability and intractability side by side, are the first ones separating Karp kernelization from Turing kernelization . This answers affirmatively an open problem regarding “cheat kernelization” raised by Mike Fellows and Jiong Guo independently.

The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop kernelization algorithms for the problem on several classes of sparse graphs. We obtain linear kernels on planar graphs, and kernels of size O(k^{3/2}) in graphs excluding some fixed graph as a minor and in graphs of bounded degeneracy. As a byproduct of our results, we obtain approximation algorithms with approximation ratios O(log{k}) on planar graphs and O(sqrt{k} log{k}) on H-minor-free graphs. These results significantly improve the previously known kernelization and approximation results for Minimum Fill-in on sparse graphs.

Potential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulation problems including Minimum Fill-in and Treewidth. We discover unexpected applications of these notions to the field of moderate exponential algorithms. In particular, we show that given an n-vertex graph G together with its set of potential maximal cliques, and an integer t, it is possible in time the number of potential maximal cliques times $O(n^{O(t)})$ to find a maximum induced subgraph of treewidth t in G and for a given graph F of treewidth t, to decide if G contains an induced subgraph isomorphic to F. Combined with an improved algorithm enumerating all potential maximal cliques in time $O(1.734601^n)$, this yields that both the problems are solvable in time $1.734601^n$ * $n^{O(t)}$.

The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least $k$ leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the {\sc $k$-Leaf-Out-Branching} problem. We give the first polynomial kernel for {\sc Rooted $k$-Leaf-Out-Branching}, a variant of {\sc $k$-Leaf-Out-Branching} where the root of the tree searched for is also a part of the input. Our kernel has cubic size and is obtained using extremal combinatorics. For the {\sc $k$-Leaf-Out-Branching} problem, we show that no polynomial kernel is possible unless the polynomial hierarchy collapses to third level by applying a recent breakthrough result by Bodlaender et al. (ICALP 2008) in a non-trivial fashion. However, our positive results for {\sc Rooted $k$-Leaf-Out-Branching} immediately imply that the seemingly intractable {\sc $k$-Leaf-Out-Branching} problem admits a data reduction to $n$ independent $O(k^3)$ kernels. These two results, tractability and intractability side by side, are the first ones separating {\it many-to-one kernelization} from {\it Turing kernelization}. This answers affirmatively an open problem regarding ``cheat kernelization'' raised by Mike Fellows and Jiong Guo independently.

We present an algorithm with runtime $O(k^{2k}n^3m)$ for the following NP-complete problem [M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, 1979, problem GT35]: Given an arbitrary graph G on n vertices and m edges, can we obtain an interval graph by adding at most k new edges to G? This resolves the long-standing open question [H. Kaplan, R. Shamir, and R. E. Tarjan, SIAM J. Comput., 28 (1999), pp. 1906–1922; R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999; M. Serna and D. Thilikos, Bull. Eur. Assoc. Theory Comput. Sci. EATCS, 86 (2005), pp. 41–65; G. Gutin, S. Szeider, and A. Yeo, in Proceedings IWPEC 2006, Lecture Notes in Comput. Sci. 4169, Springer-Verlag, Berlin, 2006, pp. 60–71], first posed by Kaplan, Shamir, and Tarjan, of whether this problem was fixed parameter tractable. The problem has applications in profile minimization for sparse matrix computations [J. A. George and J. W. H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981; R. E. Tarjan, in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, eds., Academic Press, 1976, pp. 3–22], and our results show tractability for the case of a small number k of zero elements in the envelope. Our algorithm performs bounded search among possible ways of adding edges to a graph to obtain an interval graph and combines this with a greedy algorithm when graphs of a certain structure are reached by the search.

We show that the treewidth and the minimum fill-in of an n-vertex graph can be computed in time $\mathcal{O}(1.8899^n)$. Our results are based on combinatorial proofs that an n-vertex graph has $\mathcal{O}(1.7087^n)$ minimal separators and $\mathcal{O}(1.8135^n)$ potential maximal cliques. We also show that for the class of asteroidal triple–free graphs the running time of our algorithms can be reduced to $\mathcal{O}(1.4142^n)$.

We present an algorithm with runtime O(k(2k)n3 * m) for the following NP-complete problem: Given an arbitrary graph G on n vertices and m edges, can we obtain an interval graph by adding at most k new edges to G? This resolves the long-standing open question, first posed by Kaplan, Shamir and Tarjan, of whether this problem could be solved in time f(k) * n(O(1)).The problem has applications in Physical Mapping of DNA and in Profile Minimization for Sparse Matrix Computations. For the first application, our results show tractability for the case of a small number k of false negative errors, and for the second, a small number k of zero elements in the envelope.

The problem of computing minimal triangulations of graphs, also called minimal fill, was introduced and solved in 1976 by Rose, Tarjan, and Lueker [SIAM J. Comput., 5 (1976), pp. 266-283] in time $O(nm)$ and thus $O(n^3)$ for dense graphs. Although the topic has received increasing attention since then and several new results on characterizing and computing minimal triangulations have been presented, this first time bound has remained the best. In this paper we introduce an $O(n^\alpha \log n)$ time algorithm for computing minimal triangulations, where $O(n^\alpha)$ is the time required to multiply two $n \times n$ matrices. The current best known $\alpha$ is less than $2.376$, and thus our result breaks the longstanding asymptotic time complexity bound for this problem. To achieve this result, we introduce and combine several techniques that are new to minimal triangulation algorithms, such as working on the complement of the input graph, graph search for a vertex set A that bounds the size of the connected components when A is removed, and matrix multiplication.