ALCOMFT-TR-01-112

Jochen Alber, Hans L. Bodlaender, Henning Fernau and Rolf Niedermeier
Fixed Parameter Algorithms for Planar Dominating Set and Related Problems
Utrecht. Work package 4. May 2001.

Abstract: We present an algorithm that constructively produces a solution to the k-dominating set problem for planar graphs in time O(c^\sqrt{k} n), where c=3^6\sqrt{34}. To obtain this result, we show that the treewidth of a planar graph with domination number gamma (G) is O(\sqrt{gamma (G)}), and that such a tree decomposition can be found in O(\sqrt{gamma (G)}n) time. The same technique can be used to show that the k-face cover problem (find a size k set of faces that cover all vertices of a given plane graph) can be solved in O(c₁^\sqrt{k} n +n²) time, where c₁=2^36\sqrt{34} and k is the size of the face cover set. Similar results can be obtained in the planar case for some variants of k-dominating set, e.g., k-independent dominating set and k-weighted dominating set.

Postscript file: ALCOMFT-TR-01-112.ps.gz (189 kb).