A refined search tree technique for Dominating Set on planar graphs

We establish a refined search tree technique for the parameterized D OMINATING S ET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running time...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2005-11, Vol.71 (4), p.385-405
Main Authors: Alber, Jochen, Fan, Hongbing, Fellows, Michael R., Fernau, Henning, Niedermeier, Rolf, Rosamond, Fran, Stege, Ulrike
Format: Article
Language:English
Subjects:
Dominating set
Exact algorithm
Fixed-parameter tractability
NP-complete problem
Planar graph
Search tree
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We establish a refined search tree technique for the parameterized D OMINATING S ET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O ( 8 k n ) and O ( 8 k k + n 3 ) , where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2004.03.007