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.

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