## 3 Linear Programming Approach
The LP rounding does well on sparse real-world graphs, consistent with theory, and normally outperforms the other algorithms. For hypercubes and k-Queens graphs (which are not sparse) greedy outperforms the rest, consistent with theory, both in terms of speed and performance ratio. For synthetic graphs (generated k-trees and k-planar graphs), LP rounding is outperformed by the other two algorithms, and the hybrid algorithm outperforms greedy. Throughout our experimentation, the hybrid algorithm was never the worst. The hybrid algorithm's success in solving large sparse problems suggests that more research in this area will be fruitful with respect to characterizations of parameter \(\alpha\). In particular, a theoretical research direction would be attempting to tighten the upper bound on the value of the solution computed by the hybrid algorithm, as stated in Remark 2. Can the upper bound on the value of the solution be shown to be better than \((2a+1)*\gamma(G)\) with the appropriate choice of \(\alpha\)? [PERSON] and [PERSON] wrote the code, collected and generated data, ran experiments and collected the results, and participated in analysis and writing the paper. [PERSON] conceptualized, wrote a draft of the paper, and supervised and provided guidance for the work. All authors have read and agreed to the published version of the manuscript. This research received no external funding. We thank the University of North Texas and the Texas Academy of Mathematics and Sciences for supporting our research. This work was initiated and completed at the University of North Texas and was supported in part by a TAMS summer scholarship. The authors declare no conflict of interest. ## Abbreviations

The following abbreviations are used in this manuscript: \begin{tabular}{l l} LP & Linear Programming \\ IP & Integer Programming \\ \end{tabular} 

## Appendix A

**Example A1**. : _Let \(p\geq 2\) be an integer and for \(i=1,2,\ldots,p\), let \(S_{i}\) be a star on \(2^{i}\) vertices. Consider a graph \(G\) on \(n=2^{p+1}\) vertices whose vertices are the disjoint union of the vertices of the \(S_{i}\)'s (\(i=1,2,\ldots,p\)) plus two additional vertices \(t_{1}\) and \(t_{2}\). Now, place edges from \(t_{1}\) and \(t_{2}\) to the first half of the vertices in each \(S_{i}\) (including the root), and the second half of the vertices in each \(S_{i}\), respectively. Please note that the root of each \(S_{i}\) has degree \(2^{i}\) and the degree of both \(t_{1}\) and \(t_{2}\) is \(2^{p}-1\). Initially, greedy chooses the root of \(S_{p}\) which can cover \(2^{p}+1\) vertices (including itself). Generally, at iteration \(i\geq 2\), there is a tie between the root of \(S_{p+1-i}\) and \(t_{2}\) since each can cover \(2^{p-2}\) uncovered vertices. If tie breaking does not result in selecting \(t_{2}\), there will be a tie in every iteration until the algorithm returns the set of \(S_{i}\)'s (\(i=1,2,\ldots,p\)). This dominating set has cardinality \(p=log(\Delta)-1\), but \(\gamma(G)=2\), since \(\{t_{1},t_{2}\}\) is a minimum dominating set. Please note that \(G\) is a planar graph._

**Example A2**. : _Let \(p\geq 2\) be an integer, and let \(G\) be a graph with vertices \(V_{1}\cup V_{2}\), where \(V_{1}=\{s_{1},s_{2},\ldots,s_{p},t_{1},t_{2}\}\) and \(V_{2}=\{v_{1},v_{2},\ldots,v_{2^{p+1}-2}\}\). Now make \(V_{1}\) a clique and \(V_{2}\) an independent set of vertices, respectively. Next, consider a linear ordering \(L\) on \(V_{2}\): for \(i=1,2,\ldots,p\), the set of neighbors of \(s_{i}\) in \(V_{2}\), denoted by \(W_{i}\), has cardinality \(2^{i}\) and is disjoint from \(W_{k}\), for any \(k\leq i\). Finally, for \(i=1,2,\ldots,p\) place edges between \(t_{1}\) and the first half of the vertices in each \(W_{i}\), and place edges between \(t_{2}\) and the second half of the vertices in each \(W_{i}\).