Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs excluding a single-crossing graph (a graph that can be drawn in the plane with at most one crossing) as a minor in O(49.55√knO(1)) time. Examples of such graph classes are the K3.3-minor-free graphs and the K 5-minor-free graphs. 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 collection of vertex-removal problems. Our work generalizes and extends the recent results of exponential speedup in designing fixed-parameter algorithms on planar graphs due to Alber et al. to other (nonplanar) classes of graphs.

Original languageEnglish (US)
Pages (from-to)245-267
Number of pages23
JournalAlgorithmica (New York)
Volume41
Issue number4
DOIs
StatePublished - Feb 2005

Keywords

  • Dominating set
  • Graph minors
  • Subexponential algorithms

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors'. Together they form a unique fingerprint.

Cite this