# zbMATH — the first resource for mathematics

Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs. (English) Zbl 1016.68055
Summary: 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 = 4^{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_1^{\sqrt k} n)$$ time, where $$c_1 = 3^{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.

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 68W05 Nonnumerical algorithms
Full Text: