## 3 Linear Programming Approach  
One can formulate the computation of \(\gamma(G)\) as an integer programming problem IP1 stated below. However, since integer programming problems are known to be NP-hard [20], the direct application of the integer programming method would not be computationally fruitful. Next observe that by relaxing the integer program IP1, one obtains the linear program LP1 shown below. ```
1:Minimize \(I=\sum_{o\in V}x_{v}\)  Subject to \(\sum_{u\in N[v]}x_{u}\geq 1,\forall v\in V\) \(x_{v}\in\{0,1\}\), \(\forall v\in V\)
```  
**LP1:**  
Minimize \(L=\sum_{o\in V}x_{v}\)  Subject to \(\sum_{u\in N[v]}x_{u}\geq 1,\forall v\in V\) \(0\leq x_{v}\leq 1\), \(\forall v\in V\) ```
**Algorithm 1**_Throughout rest of this paper we denote by \(L^{*}\) and \(I^{*}\) the values of \(L\) and \(I\) in LP1, and IP1, respectively, at optimality._  
Please note that \(L^{*}\leq\gamma(G)=I^{*}\). _Linear Programming Rounding_  
Algorithm \(R_{1}\) is due to [PERSON] and [PERSON] [13]. [PERSON] [14; 21] studied the \(d\)-domination problem, i.e., when a vertex dominates all vertices at distance at most \(d\) from it and its combinatorial dual, or a \(2d\)-independent set [22]. In [14] he employed the LP rounding approach of [PERSON] and [PERSON] as a part of his frame work and consequently, for \(d=1\), he improved the approximation ratio of algorithm \(R_{1}\) by showing that the algorithm \(R_{2}\) given below provides a \(2a(G)+1\) approximation. ```
1:Solve LP1, and let \(H\) be the set of all vertices that have weight at least \(1/(2a(G)+1)\), where \(a(G)\) is the arboricity of graph \(G\). Let \(U\) be the set of all vertices that are not adjacent to any vertex of \(H\) and return \(H\cup U\). ```

**Algorithm 2**_(14)_

**Remark 1**: _Graph \(G\) in Example 1 in the Appendix \(A\) is planar, so \(a(G)\leq 3\). Thus, algorithms \(R_{1}\) and \(R_{2}\) have a worst-case performance ratio of nine and seven respectively, whereas greedy exhibits a worst-case \(O(\log(n))\) performance ratio. Throughout our experiments, rounding algorithms returned an optimal solution of size two for both examples, whereas greedy returned a set of size three for Example 1. Furthermore, in Example 2 in the appendix, it can be verified that \(a(G)\geq(p+2)/2\) for graph \(G\) and hence in theory the worst-case performance ratios of the rounding algorithms are not constant either. Interestingly enough, in our experiments, \(L^{*}\) was always two for graphs of type Example 2, and LP rounding algorithms also always found a solution of size two, which is the optimal value. Thus, the performance ratio was always one, and much smaller than the predicted worst case._

## 4 Hybrid Approach

Next, we provide a description of the decomposition approach for approximating LP1 and our hybrid algorithm. Recall that a separation in \(G=(V,E)\) is a partition \(A\cup B\cup C\) of \(V\) so that no vertex of \(A\) is adjacent to any vertex of \(C\). In this case, \(B\) is called a vertex separator in \(G\). Let \(X=\{x_{v}|v\in V\}\) be a feasible solution to LP1, and let \(V^{\prime}\subseteq V\). Then \(X(V^{\prime})\) denotes \(\sum_{v\in V^{\prime}}x_{v}\). Lemma 1: _Let \(A\cup B\cup C\) be a separation in \(G=(V,E)\) and consider the following linear programs:_ \begin{tabular}{|p{227.6 pt}|} \hline
**LP2:** \\ _Minimize_ \(M=\sum_{v\in A\cup B}x_{v}\) \\ _Subject to_ \(\sum_{u\in N[v]}x_{u}\geq 1,\forall v\in A\) \\ \(0\leq x_{v}\leq 1,\ \forall v\in A\cup B\) \\ \hline \end{tabular} \begin{tabular}{|p{227.6 pt}|} \hline
**LP3:** \\ _Minimize_ \(N=\sum_{v\in B\cup C}x_{v}\) \\ _Subject to_ \(\sum_{u\in N[v]}x_{u}\geq 1,\forall v\in C\) \\ \(0\leq x_{v}\leq 1,\ \forall v\in B\cup C\) \\ \hline \end{tabular} 

_Then \(\max\{M^{*},N^{*}\}\leq L^{*}\)._

Proof: Let \(X=\{x_{v}|v\in V\}\) be an optimal solution to LP1. Please note that the restrictions of \(X\) to \(B\cup C\) and \(A\cup B\) give feasible solutions for LP3 and LP2 of values \(X(B\cup C)\) and \(X(A\cup B)\), and hence the claim for the lower bound on \(L^{*}\) follows.