## 4 Computational Study of PTAS  
We study the practical performance of the PTAS for the planar dominating set problem. The PTAS is implemented in C++ and its performance is tested for four different classes of graphs including the Delaunay triangulations of point sets taken from TSPLIB [25] (Class (1)), triangulations (Class (2)) and intersection graphs (Class (3)) generated by LEDA [26] and Gabriel graphs (Class (4)) generated using the points uniformly distributed in a two-dimensional plane. Those classes of graphs are well used in previous computational studies and the branchwidth of the graphs increases in the size of graphs (for classes of graphs with small branchwidth such as the maximal random planar graphs from LEDA [26], the FT algorithm can find optimal solutions efficiently [21] and thus they are not interesting in this study). The computer used for testing has an AMD Athlon(tm) 64 X2 Dual Core Processor 4600+ (2.4 GHz) and 3 GByte of internal memory. The operating system is SUSE Linux 10.2. We use the FT algorithm to compute an optimal solution for each \((k+2)\)-outer planar subgraph. There are three major steps of FT Algorithm:  
1. Compute a linear size kernel \(H\) of the subgraph using the \(O(n^{3})\) time kernelization algorithm by [PERSON] _et al_. [12]. 2. Compute an optimal branch-decomposition of \(H\) by the \(O(n^{3})\) time algorithm [17, 18]. 3. Find an optimal solution for \(H\) by dynamic programming based on the branch-decomposition of \(H\) and compute an optimal solution for the subgraph from the optimal solution for \(H\). Step 3 has exponential time complexity and memory complexity in the width of the branch-decomposition used, and is the dominating part in the running time and used memory of the FT algorithm. Thus we include the kernelization in the FT algorithm because, for a kernel \(H\) of a graph \(G\), \(\mathrm{bw}(H)\leq\mathrm{bw}(G)\) and it often happens that \(\mathrm{bw}(H)<\mathrm{bw}(G)\) for a kernel computed. Also, the effort for computing an optimal branch-decomposition reduces the running time and used memory in practice. For a planar graph \(G\), the FT algorithm implemented runs in \(O(2^{(3\log_{4}3)\mathrm{bw}(H)}\gamma(G)+n^{3})\) time and uses \(O(3^{\mathrm{bw}(H)}\gamma(G))\) memory space. Readers may refer to [21] for more details on the practical performance of the FT algorithm. Table 1 shows the computational results of the PTAS for the planar dominating set problem. For every instance, we calculate the approximated solutions for two different values of \(k\), 3 and 4, and, for every value of \(k\), we calculate the \((k+2)\)-outer planar decomposition for every face of the instance. We choose the best value for an approximated solution. For some instances with small branchwidth, we also include the optimal solutions computed by the FT algorithm and reported in [21] in the column of \"Exact Alg.\". The size of a minimum dominating set of graph \(G\), computed by the FT algorithm, is indicated by \(\gamma(G)\) in Table 1, and for every value of \(k\), \(D_{PTAS}\) is the size of dominating set computed by the PTAS. In the table, \(bw\) is the branchwidth of \(G\), \(\beta\) is the branchwidth of a kernel \(H\) of \(G\) in the FT algorithm and the largest branchwidth of a kernel \(H\) of a \((k+2)\)-outer planar subgraph in PTAS. The running time is in seconds. For two large instances rand16000 and rand20000, we only compute \(\gamma(G)\) but not the minimum dominating sets by the FT algorithm due to the memory constraint. These values of \(\gamma(G)\) are identified by \"*\". In order to compare the size of dominating sets obtained from the PTAS with the optimal solutions, we include some instances with small branchwidth for every class of graphs, such that a minimum dominating set can be computed by FT Algorithm. The Exact Alg. column shows the results of FT Algorithm reported in [21]. We use two values for \(k\) to decompose the instances into \((k+2)\)-outer planar component.