Computational study for domination problems in planar graphs

The DOMINATING SET problem is one of the most widely studied problems in graph theory and networking. For a graph G(V, E), D ⊆ V (G) is a dominating set of G if each vertex v of G is either in D or has a neighbour in D. Finding a minimum dominating set for arbitrary graphs is NP-hard and remains NP-hard for planar graphs. Recently, based on the notion of branch-decompositions, there has been significant theoretical progress towards fixed-parameter algorithms and polynomial time approximation schemes (PTAS) for the problem in planar graphs. However, little is known on the practical performances of those algorithms and a major hurdle for such evaluations is lack of efficient tools for computing branch-decompositions of input graphs. We develop efficient implementations of algorithms for computing optimal branch-decompositions of planar graphs. Based on these tools, we perform computational studies on a fixed-parameter exact algorithm and a PTAS for the DOMINATING SET problem in planar graphs. Our studies show that the fixed parameter exact algorithm is practical for graphs with small branchwidth and the PTAS is an efficient alternative for graphs with large branchwidth. We also perform analytical and computational studies for a branch-decomposition based fixed parameter exact algorithm for the CONNECTED DOMINATING SET (CDS) problem in planar graphs. We prove a better upper bound for the branchwidth in terms of the minimum size of CDS. Using this improved upper bound, we achieve an improved time complexity for the exact algorithm for the CDS problem. Finally, we show that the density of the CDS problem in planar graphs is 1/√5 in bidimensionality theorem.