We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of K_5 or K_(3,3) as a minor in time O(4~(16.5k~(1/2))n~O(1))), which is an exponential factor faster than the previous O(2~O(k))n~(O(1))). In fact, we present our algorithm for any H-minor-free graph where H is a single-crossing graph (can be drawn in the plane with at most one crossing) and obtain the algorithm for K_(3,3)(K_5)-minor-free graphs as a special case. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set and a series of vertex removal problems. Our work generalizes and extends the recent result of exponential speedup in designing fixed-parameter algorithms on planar graphs by Alber et al. to other (nonplanar) classes of graphs.
展开▼
