## 1 Introduction  
Domination theory has its roots in the \(k\)-Queens problem in the 18 th century. Later, in 1957, [PERSON] [1] formally introduced the domination number of a graph. A subset of vertices \(S\) in a graph \(G\) is a dominating set if every vertex not in \(S\) is adjacent to some vertex in \(S\). A dominating set of smallest cardinality is called a minimum dominating set. The cardinality of a minimum dominating set is called domination number of \(G\) and is denoted by \(\gamma(G)\). The vertices colored red in Figure 1 constitute a minimum dominating set in the graph \(Q_{3}\), or the three dimensional cube. For the remainder of the paper, we assume familiarity with general concepts of graph theory as in [2], the theory of algorithms as in [3], and linear and integer programming concepts as in [4], respectively. We refer the reader to the book by [PERSON], [PERSON], and [PERSON] [5] as a general reference in domination theory. The problem of computing the domination number of a graph is well studied, and has extensive applications, including the design of telecommunication networks, facility location, and social networks. Computing \(\gamma(G)\) is known to be an NP-hard problem, even in restricted cases, including unit disc graphs and grids [6], and hence the researchers have focused on approximation and finding a small dominating set. A simple greedy algorithm is known to approximate \(\gamma(G)\) to within a logarithmic factor from the optimal value. It is known that improving the logarithmic approximation factor is also NP-hard [7]. Hence, no algorithm for approximating \(\gamma(G)\) can improve the asymptotic worst-case performance ratio of the greedy algorithm. Different variations of this algorithm are proposed and some are tested in practice. See the work of [PERSON] [8], [PERSON] et al. [9], [PERSON] et al. [10], [PERSON] [11], and [PERSON] [12]. There are other approximation algorithms for very specific classes of graphs, including planar graphs, which have better than constant performance ratio in the worst case but are more complex than the algorithms described here. See [12] for a brief reference to some related papers. Very recently, [PERSON] and [PERSON] [13] and [PERSON] [14] showed that an appropriate rounding of solutions to the linear programming (LP) formulations for computing \(\gamma(G)\) provides dominating sets whose cardinalities are at most \(3\cdot a(G)\cdot L^{*}\) and \((2\cdot a(G)+1)\cdot L^{*}\), respectively, in polynomial time. Here, \(a(G)\) is the arboricity of \(G\), and \(L^{*}\) is the value of the optimal solution to the linear programming, which is a lower bound on \(\gamma(G)\). Hence, for graphs with bounded arboricity, one can improve the logarithmic performance ratio of the greedy algorithm to a constant. The greedy algorithm is simple, fast, and is tested in practice. One anticipates that it outperforms the LP-based approach if CPU time is the criteria. Nonetheless, its performance ratio in the worst case is logarithmic even for planar graphs which have arboricity at most 3; see example 1 in the Appendix A. For sparse graphs, the recent LP rounding methods referenced above have a bounded performance ratio, which is better than greedy, but to our knowledge, and in contrast to the greedy algorithm, the performance of the LP-based approaches have not been tested in practice. Furthermore, one would expect that for large graphs, the LP formulations would become formidable. Can one hope that a combination of these methods would give a better result than each individually, and if so, in what scenarios? In this paper, we compare and contrast the performance of the greedy algorithm, the LP rounding algorithm, and a hybrid algorithm that combines the greedy and LP approaches. Our hybrid algorithm first solves the problem using the greedy algorithm and finds a dominating set, then takes a portion of vertices in this set and forces their values to be 1 in the linear programming formulation, solves the resulting linear program, and finally properly rounds the solution.