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

Our results are obtained by considering bounded-degree minor-closed classes for which all obstructions are connected graphs, and showing that the size of any obstruction for Wk(G) is O(tk7+t7k2), where t is a bound on the size of obstructions for G. A trivial corollary of this result is an upper bound of (k+1)(k+2) on the number of vertices in any obstruction of the class of graphs with vertex cover of size at most k. These results are of independent graph-theoretic interest.