1
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ Can you provide the source of this claim (link/book/..) $\endgroup$ Mar 11, 2023 at 19:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – Highheath
    Mar 12, 2023 at 6:53
  • 1
    $\begingroup$ Cross-posted: cs.stackexchange.com/q/158968/755, math.stackexchange.com/q/4656428/14578. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Mar 12, 2023 at 7:53
  • $\begingroup$ @NarekBojikian it's nothing official, just a fellow students claim, I don't know if he relied on any supposedly reliable source. $\endgroup$ Mar 12, 2023 at 12:53
  • $\begingroup$ @D.W. got, it - I will delete the other question $\endgroup$ Mar 12, 2023 at 12:53

1 Answer 1

3
$\begingroup$

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

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 12, 2023 at 13:07
  • $\begingroup$ You're welcome. The Wikipedia page on Dominating Set is helpful. $\endgroup$ Mar 12, 2023 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.