Paper by Erik D. Demaine

Reference:

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”, in Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002), Lecture Notes in Computer Science, volume 2518, Vancouver, British Columbia, Canada, November 20–23, 2002, pages 262–273.

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(4^16.5 √k 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₅)-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 (non-planar) classes of graphs.

Comments:

This paper is also available from SpringerLink.

Copyright:

The paper is \copyright Springer-Verlag.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (200k), gzipped PostScript (78k), and PDF (225k).

See information on file formats.

[Google Scholar search]

Related papers:

CliqueSum_Algorithmica (Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors)

CliqueSum_TR2002 (Exponential Speedup of Fixed Parameter Algorithms on K_3,3-minor-free or K₅-minor-free Graphs)

CliqueSum_APPROX2002 (1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor)