Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs
Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos · DSpace@MIT (Massachusetts Institute of Technology) · 2004
... Building on these results, we develop subexponential fixed-parameter algorithms for dominating set, vertex cover, and set cover in any class of graphs excluding a fixed graph H as a minor. Inparticular, this general category of graphs includes planar graphs, bounded-genus graphs, single-crossing-minor-free graphs, and anyclass of graphs that is closed under taking minors. Specifically, the running time is 2O(pk)nh, where h is a constant depending onlyon H, which is polynomial for k = O(log² n). We introducea general approach for developing algorithms on H-minor-freegraphs, based on structural results about H-minor-free graphs at the