Dominating Set Greedy Approximation Worst-Case Example

Question

To find a minimum Dominating Set of an undirected Graph G you can use a greedy algorithm like this: Start with an empty set D. Until D is a dominating Set, add a vertex v with maximum number of uncovered neighbours.

The algorithm generally does not find the optimal solution, it is a ln(Delta)-approximation. (If Delta is the maximum degree of a vertex in G)

Now I am looking for a simple example where the greedy algorithm does not find the optimal solution. The only one I found is a related instance of the set cover problem. (http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm picture on the right) Translating this one to a graph would cause a minimum of 14 vertices and a lot of edges.

Does anyone know a small example?

Thanks in advance

Answer 1

Consider the following graph:

A greedy approach will choose B then D and G. Meanwhile, E and F form a dominating set.