From [1]}, the dominating set problem has \(\log n\)  approximation algorithm on general graphs, and it does not admit \((1-\epsilon )\log n\) -approximation algorithm in polynomial time on general graphs, for any \(\epsilon >0\) , unless NP \(\subseteq \)  DTIME \((n^{O(\log \log n)})\) . Further, it is known [2]}, that the dominating set problem is NP-complete on split graphs, and we are interested in analyzing the approximation algorithm for the dominating set problem on split graphs. In this section, we show that the dominating set problem has a \(2-\frac{1}{|I|}\)  approximation algorithm in polynomial time for split graphs. Further, it is important to highlight that in [3]}, it incorrectly claimed that split graphs does not admit \((1-\epsilon )\log n\) -approximation algorithm in polynomial time, for any \(\epsilon >0\) , unless NP \(\subseteq \)  DTIME \((n^{O(\log \log n)})\) .

The dominating set problem has \(2-\frac{1}{|I|}\)  approximation algorithm in polynomial time for split graphs.


Since the Steiner set \(S\)  obtained for STREE of \(G\)  for \(R=I\)  is a subset of \(K\) , \(S\)  is also a dominating set. We know that STREE has \(2-\frac{1}{|R|}\)  approximation algorithm in polynomial time, where \(R=I\)  for split graphs. Hence we also have \(2-\frac{1}{|I|}\)  approximation algorithm in polynomial time for split graphs.
\(\Box \)
