## 3 Linear Programming Approach
Please note that in LP2 and LP3 the constraints are not written for all variables, and the rounding method in [13] may not directly be applied. Theorem 1: _Let \(G=(V,E)\), let \(A\subset V\), let \(B=N(A)\) and let \(C=V-(A\cup B)\). Let \(X\) be an optimal solution for LP3, and let \(X(C)\) denote the sum of the weights assigned to all vertices in \(C\). Then there is a dominating set in \(G\) of size at most \(|A|+3a(G)X(C)\leq|A|+3a(G)N^{*}\)._

Proof: Let \(H\) be the set of all vertices \(v\) in \(C\) with \(x(v)\geq\frac{1}{3a}\), and let \(U=C-(H\cup N(H))\). Now apply the method in [13] to \(C\) to obtain a rounded solution, or a dominating set \(D\), of at most \(|U|+|H|\leq 3a(G)X(C)\) vertices in \(C\). Finally, note that \(A\cup D\) is a dominating set in \(G\) with cardinality at most \(|A|+3a(G)X(C)\leq|A|+3a(G)N^{*}\). **The Hybrid Algorithm:**

Fix \(0<\alpha<1\). Apply the greedy algorithm to \(G\) to obtain a dominating set \(D=\{x_{1},x_{2},\ldots,x_{d}\}\), and let \(S=\{x_{1},x_{2},\ldots,x_{a\cdot d}\}\) be the first \(\alpha\cdot d\) vertices in \(D\). Now, solve the following linear program on the induced subgraph of \(G\) with the vertex set \(V-\{S\}\). \[\text{Minimize }J = \sum_{v\in V-\{S\}}x_{v} \tag{1}\] \[\text{Subject to} \sum_{u\in N[v]}x_{u}\geq 1,\forall v\in V-\{S\cup N[S]\}\] (2) \[0\leq x_{v}\leq 1,\ \forall v\in V-S \tag{3}\]Next, let \(A=S,B=N(S)\) and \(C=V-(A\cup B)\), and apply the rounding scheme in algorithms \(R_{1}\) or \(R_{2}\) to \(C\). Let \(H\) and \(U\) be the corresponding sets, and output the set \(S\cup H\cup U\). **Remark 2**: _Please note that with Theorem 1, the hybrid algorithm can be implemented in polynomial time. Furthermore, \(|S\cup H\cup U|\leq\alpha.d+3a(G)N^{*}\leq\alpha.(ln(\Delta)+1)+3a(G)). \(\gamma(G)\), and thus the hybrid algorithm has a bounded performance ratio._

**Remark 3**: _We choose the value of \(\alpha\) by trial and error, normally starting at \(\alpha=1/2\)._

## 5 Environment, Implementation, and Datasets

We used a laptop with modest computational power--8 th generation Intel i5 (1.6 GHz) and 8 GB RAM--to perform the experiments. We implemented the \(O(n+m)\) time version of the greedy algorithm in C++. At the time of writing this paper we did not have access to packages that offer the polynomially time bounded versions of linear programming. We used IBM Decision Optimization CPLEX Modeling (DOCPLEX) for Python to solve the LP relaxation of the problem for the LP rounding and hybrid algorithms. Our data sources are listed below. [[https://github.com/joklawitter/GraphGenerators](https://github.com/joklawitter/GraphGenerators)]([https://github.com/joklawitter/GraphGenerators](https://github.com/joklawitter/GraphGenerators)) +

[[http://www.inf.udec.cl/~jtuentess/datasets/graphs.php](http://www.inf.udec.cl/~jtuentess/datasets/graphs.php)]([http://www.inf.udec.cl/~jtuentess/datasets/graphs.php](http://www.inf.udec.cl/~jtuentess/datasets/graphs.php)) +

[[http://davidchalupa.github.io/research/data/social.html](http://davidchalupa.github.io/research/data/social.html)]([http://davidchalupa.github.io/research/data/social.html](http://davidchalupa.github.io/research/data/social.html)) [8]

[[https://www.cc.gatech.edu/dimacs10/downloads.shtml](https://www.cc.gatech.edu/dimacs10/downloads.shtml)]([https://www.cc.gatech.edu/dimacs10/downloads.shtml](https://www.cc.gatech.edu/dimacs10/downloads.shtml)) [23]

The graph generator at \(\dagger\) was used to create the k-planar graphs (graphs embedded in the plane with at most \(k\) crossings per edge) and k-trees (graphs with tree width \(k\) with largest number of edges) up to 20,000 vertices. We also used publicly available Google+ and Pokec social-network graphs, a publicly available 1,000,000-vertex planar graph \(\dagger\)\(\dagger\), and real-world DIMACS Graphs with up to more than 7,700,000 vertices. Furthermore, we generated the k-Queens graphs, hypercubes (up to 12 dimensions) and graphs in Example A.1 (Figure A1) and Example A.2.