## Abstract

Preprocessing by data reduction is a simple but powerful technique used for practically solving different network problems. A number of empirical studies shows that a set of reduction rules for solving Dominating Set problems introduced by Alber, Fellows & Niedermeier leads efficiently to optimal solutions for many realistic networks. Despite of the encouraging experiments, the only class of graphs with proven performance guarantee of reductions rules was the class of planar graphs. However it was conjectured in that similar reduction rules can be proved to be efficient for more general graph classes like graphs of bounded genus. In this paper we (i) prove that the same rules, applied to any graph G of genus g, reduce the k-dominating set problem to a kernel of size O(k+g), i.e. linear kernel. This resolves a basic open question on the potential of kernel reduction for graph domination. (ii) Using such a kernel we improve the best so far algorithm for k-dominating set on graphs of genus ≤ g from 2^{O(g√k+g2)}n^{O(1)} to 2 ^{O(√gk+g)} + n^{O(1)}. (iii) Applying tools from the topological graph theory, we improve drastically the best so far combinatorial bound to the branchwidth of a graph in terms of its minimum dominating set and its genus. Our new bound provides further exponential speed-up of our algorithm for the k-dominating set and we prove that the same speed-up applies for a wide category of parameterized graph problems such as k-yertex cover, k-edge dominating set, k-vertex feedback set, k-clique transversal number and several variants of the k-dominating set problem. A consequence of our results is that the non-parameterized versions of all these problems can be solved in subexponential time when their inputs have sublinear genus.

Original language | English (US) |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Editors | Josep Díaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella |

Publisher | Springer Verlag |

Pages | 581-592 |

Number of pages | 12 |

ISBN (Print) | 3540228497 |

DOIs | |

State | Published - 2004 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 3142 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

## Keywords

- Branch-width
- Dominating set
- Parameterized algorithms
- Subexponential algorithms
- Σ-embedded graphs

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science