Can we prove the greedy algorithm archives 1.5-approximation for the Minimal Dominating Set Problem?

The following approximation algorithm for the Minimal Dominating Set Problem is said by a fellow student to be a 1.5-approximation:

1. Start with empty set $$S$$
2. As long as not all vertices are covered:
• Add a vertex that is not in $$S$$ with the most uncovered neighbors including itself.
• Mark it and all its neighbors as covered
3. return $$S$$

I can't find a proof for the approximation ratio however and my own attempts to prove it have failed so far since I lack the right approach to proof something like this.

• Can you provide the source of this claim (link/book/..) Commented Mar 11, 2023 at 19:57
• Yes, it would be interesting to know where you got that information. Not only is the claim incorrect, but Dominating Set is APX-hard, which means it's likely that no polynomial-time algorithm is able to approximate this problem to a constant ratio. Commented Mar 12, 2023 at 6:53
• – D.W.
Commented Mar 12, 2023 at 7:53
• @NarekBojikian it's nothing official, just a fellow students claim, I don't know if he relied on any supposedly reliable source. Commented Mar 12, 2023 at 12:53
• @D.W. got, it - I will delete the other question Commented Mar 12, 2023 at 12:53

(Check for yourself that each run is a valid possible execution of the algorithm.) The first run chooses a solution of size 7; the second, an (optimal) solution of size 4. $$7/4 = 1.75 > 1.5$$, meaning the greedy algorithm is capable of producing a solution that violates the claimed bound.
• Thank you very much. That seems to indicate that the algorithm could be a 2-approximation since your example could be expanded to something similar but with the optimal solution being n and the worst case being $(2n-1)/(n)$, however Highheath states under my question, that a constant ratio approximation is unlikely to exist . I'm afraid, I am still missing an approach to determine and proof the actual approximation ratio. Commented Mar 12, 2023 at 13:07