Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover

Our goal in this paper is the development of fast algorithms for recognizing general classes of graphs. We seek algorithms whose complexity can be expressed as a linear function of the graph size plus an exponential function of k, a natural parameter describing the class. Our classes are of the form W_k(G), graphs that can be formed by augmenting graphs in G by adding at most k vertices (and incident edges). If G is the class of edgeless graphs, W_k(G) is the class of graphs with a vertex cover of size at most k. We describe a recognition algorithm for W_k(G) running in time O((g + k)|V (G)| + (fk)^k), where g and f are modest constants depending on the class G, when G is a minor-closed class such that each graph in G has bounded maximum degree, and all obstructions of G (minor-minimal graphs outside G) are connected. If G is the class of graphs with maximum degree bounded by D (not closed under minors), we can still recognize graphs in W_k(G) in time O(|V (G)|(D + k) + k(D + k)^k+3). Our results are obtained by considering minor-closed classes G for which all obstructions are connected graphs, and showing that the size of any obstruction for W_k(G) is O(tk⁷+ t⁷k²), where t is a bound on the size of obstructions for G.