## 3 Linear Programming Approach
**Remark 4**: _Throughout our experiments, the value of the solution computed by rounding algorithm \(R_{2}\) was always better than the value of the solution computed by rounding algorithm \(R_{1}\), as predicted in theory. Likewise, the value of the solution computed by the hybrid algorithm using \(R_{2}\) was always better compared to when \(R_{1}\) was used. Throughout sections six through nine (tables), \(r\) denotes the value of the solution computed by \(R_{2}\), and \(h\) denotes the value of the solution computed by the hybrid algorithm associated with \(R_{2}\). We denote by \(g\) the value of the solution computed by the greedy algorithm. Throughout the tables in sections six through nine, the best computed values are bolded._

## 6 Performance on k-Planar Graphs and k-Trees

In this section, we compare the performance ratios of the greedy, LP rounding and hybrid algorithms on k-planar graphs and k-trees. In all cases, the hybrid algorithm performed better than the others. Greedy performed close to hybrid and LP rounding performed the worst. The arboricity of each of the planar graphs is at most 3. For k-trees, we use \(\lceil k-\frac{(k/2)(k-1)}{n-1}\rceil\) for arboricity. For k-planar graphs, \(k\geq 1\), we use the upper bound of \(\lceil 8\sqrt{k}\rceil\) on arboricity. The k-planar graphs and k-trees were all made using \(\dagger\) described in Section 5. The typical value of \(\alpha\) was \(1/2\), but increasing it to \(3/4\) resulted in better performance in some cases. All algorithms were able to compute dominating sets in less than 2 s in all cases. ### Performance on Sparse k-Planar Graphs and k-Trees

In Tables 1-3, we present the performance of the algorithms on sparse k-planar graphs and sparse k-trees. ## 7 Performance on Hypercubes and k-Queen Graphs

In this section, we present the performance of the greedy, rounding, and hybrid algorithms on hypercubes from \(d=5\) to \(12\) dimensions and k-Queens graphs. Table 6 contains the results for hypercubes. We use the arboricity for hypercubes \(a=\lfloor d/2+1\rfloor\) for LP rounding and hybrid [24]. For k-Queens graphs, arboricity is unknown, so we use the upper bound \(3(k-1)\), where \(k\) is the length of the chessboard. For both Table 6 and 7, greedy performs the best, followed by hybrid. Rounding algorithms perform the worst by far. This is not surprising as LP rounding approaches are known to in general perform worse on dense graphs than sparse graphs. The chosen value of \(\alpha\) was always \(1/2\). Solutions were computed in under \(8\) s for all graphs and algorithms. ## 8 Performance on Real-World Graphs

In this section, we present the performance of LP rounding, greedy, and hybrid on the real-world social network graphs from DIMACS [23], Google+ [8], and Pokec [8]. All of these graphs are sparse, but their arboricity is unknown. Since arboricity is unknown, we experiment with the threshold applied during LP rounding. Through experimentation, the best threshold which we found for rounding was \(2/a^{\prime}\), where \(a^{\prime}=\lceil m/(n-1)\rceil\). We denote the value of the solution computed by the LP rounding \begin{table}
\begin{tabular}{r r r r r r} \hline \hline
**Dimension** & \(n\) & \(L^{\star}\) & \(g/L^{\star}\) & \(r/L^{\star}\) & \(h/L^{\star}\) \\ \hline
5 & 32 & 5.33 & **1.50** & 3.00 & **1.50** \\
6 & 64 & 9.14 & **1.75** & 7.00 & **1.75** \\
7 & 128 & 16.00 & **1.00** & **1.00** & **1.00** \\
8 & 256 & 28.44 & **1.13** & 9.00 & **1.13** \\
9 & 512 & 51.20 & **1.25** & 7.07 & 2.99 \\
10 & 1024 & 93.09 & **1.38** & 11.00 & 2.70 \\
11 & 2048 & 170.67 & **1.50** & 6.59 & 2.85 \\
12 & 4096 & 315.08 & **1.63** & 13.00 & 3.14 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Results for Hypercubes.