ALCOMFT-TR-02-112

Erik D. Demaine, MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos
Exponential Speedup of Fixed Parameter Algorithms on K_3,3-minor-free or K₅-minor-free Graphs
Barcelona. Work package 2. May 2002.

Abstract: We present a fixed parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of the K₅ or K_3,3 as a minor in time O(3^{6\sqrt{34 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 on the plane with at most one crossing) and obtain the algorithm for K_3,3(K₅)-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 due to Alber et al. to other (non-planar) classes of graphs.

Postscript file: ALCOMFT-TR-02-112.ps.gz (104 kb).