## 3 Linear Programming Approach
\begin{table}
\begin{tabular}{r r r r r r} \hline \hline \(n\) & \(m\) & \(L^{\star}\) & \(g/L^{\star}\) & \(r/L^{\star}\) & \(h/L^{\star}\) \\ \hline
2000 & 13,972 & 15.00 & 1.07 & 1.20 & **1.00** \\
4000 & 31,964 & 10.00 & **1.00** & **1.00** & **1.00** \\
6000 & 53,955 & 11.00 & **1.00** & **1.00** & **1.00** \\
8000 & 71,955 & 13.00 & **1.00** & **1.00** & **1.00** \\
10,000 & 99,945 & 11.19 & **1.07** & 2.23 & **1.07** \\
12,000 & 119,945 & 12.00 & **1.00** & **1.00** & **1.00** \\
14,000 & 139,945 & 18.50 & **1.08** & 1.89 & **1.08** \\
16,000 & 175,934 & 11.25 & **1.16** & 1.60 & **1.16** \\
18,000 & 197,934 & 11.00 & **1.18** & 2.00 & **1.18** \\
20,000 & 219,934 & 10.50 & **1.14** & 1.43 & **1.14** \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Results for k-Trees where \(k=\lfloor n^{0.25}\rfloor\). algorithm with this threshold as \(r^{\prime}\) and the value of the solution computed by the hybrid algorithm with this threshold as \(h^{\prime}\). The chosen value of \(\alpha\) was \(1/2\) in all cases. Table 8 contains the results for three sparse social network graphs from DIMACS. LP rounding performs better than the greedy and hybrid approaches, with greedy ranking last out of the algorithms tested. In Tables 9 and 10, we compare \(r^{\prime}\), \(h^{\prime}\), and \(g\) on the Google+ and Pokec graphs. The performance ratios, although different, happen to be very close. Thus, we list the actual sizes of the dominating sets returned by the algorithms. Compared to the best results from [8], which used a randomized local search algorithm that is run for up to one hour, LP rounding approaches generally produced, with the exception of a few cases, a smaller or as good solution using significantly less cpu-time at less than \(0.5\) s for each graph. ## 9 Very Large Sparse Graphs

Table 11 contains the results on a 7 million+ vertices graph (Great Britain street network) and a 1 million vertices planar graph, where we used Lemma 1 to compute \(Z=max\{M^{*},N^{*}\}\). The LP solver crashed when it was directly applied to the Great Britain street network and took over 3.5 h of CPU time to compute an answer on the 1 million vertices planar graph. Through a search for \(\alpha\), we came up with \(\alpha=3/4\) for hybrid. The hybrid algorithm's performance ratio to \(Z\) was better than greedy's. Greedy took 14 s to produce a solution while hybrid took 107 s on the street network graph. On the 1 million vertices planar graph, greedy took 4 s and hybrid took 19 s. \begin{table}
\begin{tabular}{r r r r r r} \hline \hline \(n\) & \(m\) & \(L^{*}\) & \(g\) & \(r^{\prime}\) & \(h^{\prime}\) \\ \hline
500 & 1006 & 42 & **42** & **42** & **42** \\
2000 & 5343 & 170 & 176 & **170** & 176 \\
10,000 & 33,954 & 860 & 900 & **864** & 893 \\
20,000 & 81,352 & 1715 & 1817 & **1716** & 1800 \\
50,000 & 231,583 & 4565 & 4849 & **4585** & 4790 \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Results for _Google+_ Graphs. \begin{table}
\begin{tabular}{r r r r r r r} \hline \hline
**Graph** & \(n\) & \(m\) & \(L^{*}\) & \(g\) & \(h^{\prime}\) & \(g\)/\(Z\) & \(h^{\prime}\)/\(Z\) \\ \hline GeoAuthorsDBLP & 299,067 & 977,676 & 43,969.00 & 1.02 & **1.00** & 1.02 \\ coPapersCiteseer & 434,102 & 16,036,720 & 26,040.92 & 1.12 & **1.01** & 1.12 \\ citationCiteseer & 268,495 & 1,156,647 & 43,318.85 & 1.04 & **1.02** & 1.04 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Results for DIMACS Graphs. \begin{table}
\begin{tabular}{r r r r r r} \hline \hline \(n\) & \(m\) & \(L^{*}\) & \(g\) & \(r^{\prime}\) & \(h^{\prime}\) \\ \hline
500 & 1006 & 42 & **42** & **42** & **42** \\
2000 & 5343 & 170 & 176 & **170** & 176 \\
10,000 & 33,954 & 860 & 900 & **864** & 893 \\
20,000 & 81,352 & 1715 & 1817 & **1716** & 1800 \\
50,000 & 231,583 & 4565 & 4849 & **4585** & 4790 \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Results for _Pokec_ Graphs. ## 10 Conclusions

Our findings indicate that all of these algorithms perform better than anticipated in theory, particularly with respect to the performance ratio.