I am writing an algorithm to find the dominating set of a tournament graph. Is the minimum spanning tree of a directed graph equivalent to the dominating set of the graph? In other words, if I find the smallest MST for the tournament graph (by iterating through all of the vertices), can I then say this is equivalent to the dominating set of the graph?
A:
No, because the MST will include all vertices of the graph, and the dominating set might not.
See for example the graph here: http://en.wikipedia.org/wiki/Tournament_(graph_theory)
Vertices 2 and 4 create a dominating set, and not a spanning tree.
DanJ
2008-11-17 18:38:52
I have not yet figured out how to get Wikipedia URLs with parentheses to come out properly in SO. Any suggestions?
sep332
2008-11-17 18:44:00
s/\(/%28/; s/\)/%29/
J.F. Sebastian
2008-11-17 18:51:08
+2
A:
This Wikipedia article states that the problems of finding a dominating set and finding a spanning tree are equivalent. Given a spanning tree, the non-leaf nodes form a dominating set, and given a connected dominating set, you can easily obtain of the original graph joining one spanning tree of it with the vertexes that do not belong to it. However, finding a minimum spanning tree and finding a minimal dominating set are different problems. I guess that they are equivalent again, but I'm not sure.
Federico Ramponi
2008-11-17 19:01:53
Not equivalent - Minimum Dominating Set is NP complete, Minimum spanning tree is solvable by Prim's or Kruskal's algorithm, at a cost of O(V^2)
Thelema
2010-05-17 03:42:18