The Optimal Morse Matching (OMM) problem asks for a discrete gradient vector field on a simplicial complex that minimizes the number of critical simplices. It is NP-hard and has been studied extensively in heuristic, approximation, and parameterized complexity settings. Parameterized by treewidth k, OMM has long been known to be solvable on triangulations of 3-manifolds in 2^O(k²) n^O(1) time and in FPT time for triangulations of arbitrary manifolds, but the exact dependence on k has remained an open question. We resolve this by giving a new 2^O(k log k) n-time algorithm for any finite regular CW complex, and show that no 2^o(k log k) n^O(1)-time algorithm exists unless the Exponential Time Hypothesis (ETH) fails.

Abstract We initiate the study of theDiverse Pair of (Maximum/ Perfect) Matchingsproblems which given a graphGand an integerk, ask whetherGhas two (maximum/perfect) matchings whose symmetric difference is at leastk.Diverse Pair of Matchings(asking for two not necessarily maximum or perfect matchings) is $$\textsf{NP}$$ NP -complete on general graphs ifkis part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show thatDiverse Pair of Maximum Matchingsis $$\textsf{FPT}$$ FPT parameterized byk. We round off the work by showing thatDiverse Pair of Matchingshas a kernel on $${\mathcal {O}}(k^2)$$ O(k2) vertices.

Abstract A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with q colors. For fixed $$q \ge 2$$ q ≥ 2 , we give an $$\mathscr {O}^{\star }(q^{{\mathsf {tw}}})$$ O ⋆ ( q tw ) -time algorithm when the input graph is given together with one of its tree decompositions of width $${\mathsf {tw}} $$ tw . We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) Clique Coloring is $$\mathsf {XP}$$ XP parameterized by clique-width.

We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse Bases problem consists of a matroid M, a weight function ω:E(M)→N, and integers k ≥ 1, d ≥ 0. The task is to decide if there is a collection of k bases B_1, ..., B_k of M such that the weight of the symmetric difference of any pair of these bases is at least d. This is a diverse variant of the classical matroid base packing problem. The input to the Weighted Diverse Common Independent Sets problem consists of two matroids M₁,M₂ defined on the same ground set E, a weight function ω:E→N, and integers k ≥ 1, d ≥ 0. The task is to decide if there is a collection of k common independent sets I_1, ..., I_k of M₁ and M₂ such that the weight of the symmetric difference of any pair of these sets is at least d. This is motivated by the classical weighted matroid intersection problem. The input to the Diverse Perfect Matchings problem consists of a graph G and integers k ≥ 1, d ≥ 0. The task is to decide if G contains k perfect matchings M_1, ..., M_k such that the symmetric difference of any two of these matchings is at least d. The underlying problem of finding one solution (basis, common independent set, or perfect matching) is known to be doable in polynomial time for each of these problems, and Diverse Perfect Matchings is known to be NP-hard for k = 2. We show that Weighted Diverse Bases and Weighted Diverse Common Independent Sets are both NP-hard. We show also that Diverse Perfect Matchings cannot be solved in polynomial time (unless P=NP) even for the case d = 1. We derive fixed-parameter tractable (FPT) algorithms for all three problems with (k,d) as the parameter. The above results on matroids are derived under the assumption that the input matroids are given as independence oracles. For Weighted Diverse Bases we present a polynomial-time algorithm that takes a representation of the input matroid over a finite field and computes a poly(k,d)-sized kernel for the problem.

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T − S is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here, the input is a tournament T and a weight function w : V ( T ) → N, and the task is to find a feedback vertex set S in T minimizing w ( S ) = ∑ v∈S w ( v ). Rounding optimal solutions to the natural LP-relaxation of this problem yields a simple 3-approximation algorithm. This has been improved to 2.5 by Cai et al. [SICOMP 2000], and subsequently to 7/3 by Mnich et al. [ESA 2016]. In this article, we give the first polynomial time factor 2-approximation algorithm for this problem. Assuming the Unique Games Conjecture, this is the best possible approximation ratio achievable in polynomial time.

In the Split Vertex Deletion (SVD) problem, the input is an n-vertex undirected graph G and a weight function w: V(G) → ℕ, and the objective is to find a minimum weight subset S of vertices such that G-S is a split graph (i.e., there is bipartition of V(G-S) = C ⊎ I such that C is a clique and I is an independent set in G-S). This problem is a special case of 5-Hitting Set and consequently, there is a simple factor 5-approximation algorithm for this. On the negative side, it is easy to show that the problem does not admit a polynomial time (2-δ)-approximation algorithm, for any fixed δ > 0, unless the Unique Games Conjecture fails. We start by giving a simple quasipolynomial time (n^O(log n)) factor 2-approximation algorithm for SVD using the notion of clique-independent set separating collection. Thus, on the one hand SVD admits a factor 2-approximation in quasipolynomial time, and on the other hand this approximation factor cannot be improved assuming UGC. It naturally leads to the following question: Can SVD be 2-approximated in polynomial time? In this work we almost close this gap and prove that for any ε > 0, there is a n^O(log 1/(ε))-time 2(1+ε)-approximation algorithm.

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. We consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. Our main contribution is an algorithmic framework which --automatically-- converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter.

We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP-complete on general graphs if k is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by k. We round off the work by showing that Diverse Pair of Matchings has a kernel on 𝒪(k²) vertices.

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T – S is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here the input is a tournament T and a weight function w: V(T) → ℕ and the task is to find a feedback vertex set S in T minimizing w(S) = ΣvϵSw(v). Rounding optimal solutions to the natural LP-relaxation of this problem yields a simple 3-approximation algorithm. This has been improved to 2.5 by Cai et al. [SICOMP 2000], and subsequently to 7/3 by Mnich et al. [ESA 2016]. In this paper we give the first polynomial time factor 2 approximation algorithm for this problem. Assuming the Unique Games conjecture, this is the best possible approximation ratio achievable in polynomial time.

Feedback Vertex Set (FVS) is one of the most well-studied problems in the realm of parameterized complexity. In this problem we are given a graph $G$ and a positive integer $k$ and the objective is to test whether there exists $S\subseteq V(G)$ of size at most $k$ such that $G-S$ is a forest. Thus, FVS is about deleting as few vertices as possible to get a forest. The main goal of this paper is to study the following interesting problem: How can we generalize the family of forests such that the nice structural properties of forests and the interesting algorithmic properties of FVS can be extended to problems on this class? Toward this we define a graph class, ${\cal F}_l$, that contains all graphs where each connected component can be transformed into a forest by deleting at most $l$ edges. A graph in the class ${\cal F}_1$ is known as pseudoforest in the literature and we call a graph in ${\cal F}_l$ an $l$-pseudoforest. We study the problem of deleting $k$ vertices to get into ${\cal F}_l$, l-pseudoforest Deletion, in the realm of parameterized complexity. We show that l-pseudoforest Deletion admits an algorithm with running time $c_l^k n^{\mathcal{O}(1)}$ and admits a kernel of size $f(l)k^2$. Thus, for every fixed $l$ we have a kernel of size $\mathcal{O}(k^2)$. That is, we get a uniform polynomial kernel for l-pseudoforest Deletion. Our algorithms and uniform kernels involve the use of the expansion lemma and protrusion machinery.

The standard parameterization of the Vertex Cover problem (Given an undirected graph G and k ∊ ℕ as input, does G have a vertex cover of size at most k?) has the solution size k as the parameter. The following more challenging parameterization of Vertex Cover stems from the observation that the size MM of a maximum matching of G lower-bounds the size of any vertex cover of G: Does G have a vertex cover of size at most MM + kμ? The parameter is the excess kμ of the solution size over the lower bound MM. Razgon and O'Sullivan (ICALP 2008) showed that this above-guarantee parameterization of Vertex Cover is fixed-parameter tractable and can be solved in time *(15kμ), where the * notation hides polynomial factors. This was first improved to *(9kμ) (Raman et al., ESA 2011), then to *(4kμ) (Cygan et al., IPEC 2011, TOCT 2013), then to *(2.618kμ) (Narayanaswamy et al., STACS 2012) and finally to the current best bound *(2.3146kμ) (Lokshtanov et al., TALG 2014). The last two bounds were in fact proven for a different parameter: namely, the excess kλ of the solution size over LP, the value of the linear programming relaxation of the standard LP formulation of Vertex Cover. Since LP ≥ MM for any graph, we have that kλ ≤ kμ for Yes instances. This is thus a stricter parameterization—the new parameter is, in general, smaller—and the running times carry over directly to the parameter kμ. We investigate an even stricter parameterization of Vertex Cover, namely the excess of the solution size over the quantity (2LP – MM). We ask: Given a graph G and ∊ ℕ as input, does G have a vertex cover of size at most (2LP – MM) + ? The parameter is . It can be shown that (2LP – MM) is a lower bound on vertex cover size, and since LP ≥ MM we have that (2LP – MM) ≥ LP, and hence that ≤ kλ holds for Yes instances. Further, (kλ – ) could be as large as (LP – MM) and—to the best of our knowledge—this difference cannot be expressed as a function of kλ alone. These facts motivate and justify our choice of parameter: this is indeed a stricter parameterization whose tractability does not follow directly from known results. We show that Vertex Cover is fixed-parameter tractable for this stricter parameter : We derive an algorithm which solves Vertex Cover in time *(3 ), thus pushing the envelope further on the parameterized tractability of Vertex Cover.

We study a general class of problems called $\mathcal{F}$-Deletion problems. In an $\mathcal{F}$-Deletion problem, we are asked whether a subset of at most $k$ vertices can be deleted from a graph $G$ such that the resulting graph does not contain as a minor any graph from the family ${\cal F}$ of forbidden minors. We study the problem parameterized by $k$, using $p$-$\mathcal{F}$-Deletion to refer to the parameterized version of the problem. We obtain a number of algorithmic results on the $p$-$\mathcal{F}$-Deletion problem when $\mathcal{F}$ contains a planar graph. We give a linear vertex kernel on graphs excluding $t$-claw $K_{1,t}$, the star with $t$ leaves, as an induced subgraph, where $t$ is a fixed integer and an approximation algorithm achieving an approximation ratio of $O(\log^{3/2} OPT)$, where $OPT$ is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when $\cal F$ only contains graph $\theta_c$ as a minor for a fixed integer $c$. The graph $\theta_c$ consists of two vertices connected by $c$ parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as Vertex Cover, Feedback Vertex Set, and Diamond Hitting Set. The generic kernelization algorithm is based on a nontrivial application of protrusion techniques, previously used only for problems on topological graph classes.

The input to the NP-hard point line cover problem (PLC) consists of a set P of n points on the plane and a positive integer k ; the question is whether there exists a set of at most k lines that pass through all points in P . By straightforward reduction rules, one can efficiently reduce any input to one with at most k 2 points. We show that this easy reduction is already essentially tight under standard assumptions. More precisely, unless the polynomial hierarchy collapses to its third level, for any ϵ > 0, there is no polynomial-time algorithm that reduces every instance ( P , k ) of PLC to an equivalent instance with O ( k 2 −ϵ) points. This answers, in the negative, an open problem posed by Lokshtanov [2009]. Our proof uses the notion of a kernel from parameterized complexity, and the machinery for deriving lower bounds on the size of kernels developed by Dell and van Melkebeek [2010, 2014]. It has two main ingredients: We first show, by reduction from vertex cover , that—unless the polynomial hierarchy collapses—PLC has no kernel of total size O ( k 2 −ϵ) bits. This does not directly imply the claimed lower bound on the number of points , since the best-known polynomial-time encoding of a PLC instance with n points requires ω( n 2 ) bits. To get around this hurdle, we build on work of Alon [1986] and devise an oracle communication protocol of cost O ( n log n ) for PLC. This protocol, together with the lower bound on the total size (which also holds for such protocols), yields the stated lower bound on the number of points. While a number of essentially tight polynomial lower bounds on total sizes of kernels are known, our result is—to the best of our knowledge—the first to show a nontrivial lower bound for structural/secondary parameters. It is also the first example of a lower bound for kernelization that makes use of the full power of the oracle communication protocol lower bounds that can be obtained from the work of Dell and van Melkebeek. We combine the main abstract ideas of our proof to derive a general recipe that could be used to obtain such lower bounds for other problems with unknown or insufficiently strong encodings.

Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on $n$ vertices and a positive integer parameter $k$, find if there exist $k$ edges (arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees---where the resulting graph is \emph{Eulerian}---the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al. [\emph{Algorithmica, 2014}] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time $2^{O(k \log k)}n^{O(1)}$. They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. In this paper we answer their question in the affirmative: using the technique of computing \emph{representative families of co-graphic matroids} we design algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.

The b-chromatic number of a graph G, chi_b(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the B-Chromatic Number problem, the objective is to decide whether chi_b(G) >= k. Testing whether chi_b(G)=Delta(G)+1, where Delta(G) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvil, Tuza and Voigt, WG 2002). In this paper we study B-Chromatic Number in the realm of parameterized complexity and exact exponential time algorithms. We show that B-Chromatic Number is W[1]-hard when parameterized by k, resolving the open question posed by Havet and Sampaio (Algorithmica 2013). When k=Delta(G)+1, we design an algorithm for B-Chromatic Number running in time 2^{O(k^2 * log(k))}*n^{O(1)}. Finally, we show that B-Chromatic Number for an n-vertex graph can be solved in time O(3^n * n^{4} * log(n)).

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.

The input to the NP-hard Point Line Cover problem (PLC) consists of a set of n points on the plane and a positive integer k, and the question is whether there exists a set of at most k lines which pass through all points in . By straightforward reduction rules one can efficiently reduce any input to one with at most k2 points. We show that this easy reduction is already essentially tight under standard assumptions. More precisely, unless the polynomial hierarchy collapses to its third level, for any ∊ > 0, there is no polynomial-time algorithm that reduces every instance ( , k) of PLC to an equivalent instance with (k2–∊) points. This answers, in the negative, an open problem posed by Lokshtanov (PhD Thesis, 2009). Our proof uses the notion of a kernel from parameterized complexity, and the machinery for deriving lower bounds on the size of kernels developed by Dell and van Melkebeek (STOC 2010). It has two main ingredients: We first show, by reduction from Vertex Cover, that—unless the polynomial hierarchy collapses—PLC has no kernel of total size (k2–∊) bits. This does not directly imply the claimed lower bound on the number of points, since the best known polynomial-time encoding of a PLC instance with n points requires ω(n2) bits. To get around this hurdle we build on work of Goodman, Pollack and Sturmfels (STOC 1989) and devise an oracle communication protocol of cost (nlogn) for PLC; its main building blocks are a bound of (nO(n)) for the order types of n points that are not necessarily in general position and an explicit (albeit slow) algorithm that enumerates a superset of size nO(n) of all possible order types of n points. This protocol, together with the lower bound on the total size (which also holds for such protocols), yields the stated lower bound on the number of points. While a number of essentially tight polynomial lower bounds on total sizes of kernels are known, our result is—to the best of our knowledge—the first to show a nontrivial lower bound for structural/secondary parameters.

Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0<lambda<1 and lambda-extendible property Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda*m+(1-lambda)(n-1)/2 edges. The property of being bipartite is lambda-extendible for lambda =1/2, and so the Poljak-Turzik bound generalizes the well-known Edwards-Erdos bound for Max Cut. Other examples of lambda-extendible properties include: being an acyclic oriented graph, a balanced signed graph, or a q-colorable graph for some q in N. Mnich et al. (FSTTCS 2012) defined the closely related notion of strong lambda-extendibility. They showed that the problem of finding a subgraph satisfying a given strongly lambda-extendible property Pi is fixed-parameter tractable (FPT) when parameterized above the Poljak-Turzik bound---does there exist a spanning subgraph H of a connected graph G such that H in Pi and H has at least lambda*m+(1-lambda)(n-1)/2+k edges?---subject to the condition that the problem is FPT on a certain simple class of graphs called almost-forests of cliques. This generalized an earlier result of Crowston et al. (ICALP 2012) for Max Cut, to all strongly lambda-extendible properties which satisfy the additional criterion. In this paper we settle the kernelization complexity of nearly all problems parameterized above Poljak-Turzik bounds, in the affirmative. We show that these problems admit quadratic kernels (cubic when lambda=1/2), without using the assumption that the problem is FPT on almost-forests of cliques. Thus our results not only remove the technical condition of being FPT on almost-forests of cliques from previous results, but also unify and extend previously known kernelization results in this direction. Our results add to the select list of generic kernelization results known in the literature.

Poljak and Turzík (Discrete Math. 1986) introduced the notion of lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0 < lambda < 1 and lambda-extendible property Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda m+ (1-lambda)/2 (n-1) edges. The property of being bipartite is lambda-extendible for lambda=1/2, and thus the Poljak-Turzík bound generalizes the well-known Edwards-Erdos bound for MAXCUT. We define a variant, namely strong lambda-extendibility, to which the Poljak-Turzík bound applies. For a strong lambda-extendible graph property \Pi, we define the parameterized Above Poljak-Turzík problem as follows: Given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that H in Pi and H has at least lambda m+ (1-lambda)/2 (n-1)+k edges? The parameter is k, the surplus over the number of edges guaranteed by the Poljak-Turzík bound. We consider properties Pi for which the Above Poljak-Turzík problem is fixed-parameter tractable (FPT) on graphs which are O(k) vertices away from being a graph in which each block is a clique. We show that for all such properties, Above Poljak-Turzík is FPT for all 0< lambda <1. Our results hold for properties of oriented graphs and graphs with edge labels. Our results generalize the recent result of Crowston et al. (ICALP 2012) on MAXCUT parameterized above the Edwards-Erdos, and yield FPT algorithms for several graph problems parameterized above lower bounds. For instance, we get that the above-guarantee Max q-Colorable Subgraph problem is FPT. Our results also imply that the parameterized above-guarantee Oriented Max Acyclic Digraph problem thus solving an open question of Raman and Saurabh (Theor. Comput. Sci. 2006).

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.

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.

We study a general class of problems called F-deletion problems. In an F-deletion problem, we are asked whether a subset of at most $k$ vertices can be deleted from a graph $G$ such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We obtain a number of algorithmic results on the F-deletion problem when F contains a planar graph. We give (1) a linear vertex kernel on graphs excluding $t$-claw $K_{1,t}$, the star with $t$ leves, as an induced subgraph, where $t$ is a fixed integer. (2) an approximation algorithm achieving an approximation ratio of $O(\log^{3/2} OPT)$, where $OPT$ is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F contains graph $θ_c$ as a minor for a fixed integer $c$. The graph $θ_c$ consists of two vertices connected by $c$ parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as {\sc Vertex Cover}, {\sc Feedback Vertex Set} and Diamond Hitting Set. The generic kernelization algorithm is based on a non-trivial application of protrusion techniques, previously used only for problems on topological graph classes.

In the Connected Dominating Set problem we are given as input a graph $G$ and a positive integer $k$, and are asked if there is a set $S$ of at most $k$ vertices of $G$ such that $S$ is a dominating set of $G$ and the subgraph induced by $S$ is connected. This is a basic connectivity problem that is known to be NP-complete, and it has been extensively studied using several algorithmic approaches. In this paper we study the effect of excluding short cycles, as a subgraph, on the kernelization complexity of Connected Dominating Set. Kernelization algorithms are polynomial-time algorithms that take an input and a positive integer $k$ (the parameter) and output an equivalent instance where the size of the new instance and the new parameter are both bounded by some function $g(k)$. The new instance is called a $g(k)$ kernel for the problem. If $g(k)$ is a polynomial in $k$ then we say that the problem admits polynomial kernels. The girth of a graph $G$ is the length of a shortest cycle in $G$. It turns out that Connected Dominating Set is ``hard'' on graphs with small cycles, and becomes progressively easier as the girth increases. More specifically, we obtain the following interesting trichotomy: Connected Dominating Set (a) does not have a kernel of any size on graphs of girth $3$ or $4$ (since the problem is W[2]-hard); (b) admits a $g(k)$ kernel, where $g(k)$ is $k^{O(k)}$, on graphs of girth $5$ or $6$ but has no polynomial kernel (unless the Polynomial Hierarchy (PH) collapses to the third level) on these graphs; (c) has a cubic ($O(k^3)$) kernel on graphs of girth at least $7$. While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors, our results add to the very few known in the field for graph classes characterized by excluded subgraphs.