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

Question

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.

Answer 1

This claim is incorrect. The diagram below shows a small counterexample:

Consider two different runs of the greedy algorithm that break ties in different ways:

1. Run 1 chooses the 6 red vertices in order from darkest to lightest, then chooses the yellow vertex.
2. Run 2 chooses the 3 green vertices in order from darkest to lightest, then chooses the yellow vertex.

(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.