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

Let \(W_k(\mathcal G)\) be a class of graphs, where for each graph \(G\) in \(W_k(\mathcal G)\), the removal of a set of at most \(k\) vertices from \(G\) results in a graph in the base graph class \(\mathcal G\). When \(\mathcal G\) is a minor-closed class such that each graph in \(\mathcal G\) has bounded maximum degree, and all obstructions of \(\mathcal G\) (minor-minimal graphs outside \(\mathcal G\)) are connected, the authors obtain an \(O((g+k)| V(G)| +(fk)^k)\) recognition algorithm for \(W_k(\mathcal G)\), where \(g\) and \(f\) are constants depending on \(\mathcal G\). If \(\mathcal G\) is the class of graphs with maximum degree bounded by \(D\) (not closed under minors), the authors obtain a running time of \(O(| V(G)| (D+k)+k(D+k)^{k+3})\) for recognition of graphs in \(W_k(\mathcal G)\). The authors also show that the size of any obstruction for \(W_k(\mathcal G)\) is \(O(tk^7+t^7k^2)\), where \(t\) is a bound on the size of obstructions for \(\mathcal G\) and that an upper bound on the number of vertices in any obstruction of the class of graphs with vertex cover of size at most \(k\) is \((k+1)(k+2)\).