  We investigate the problem of simultaneously dominating all spanning trees of
a given graph. We prove that on 2-connected graphs, a subset of the vertices
dominates all spanning trees of the graph if and only if it is a vertex cover.
Using this fact we present an exact algorithm that finds a simultaneous
dominating set of minimum size using an oracle for finding a minimum vertex
cover. The algorithm can be implemented to run in polynomial time on several
graph classes, such as bipartite or chordal graphs. We prove that there is no
polynomial time algorithm that finds a minimum simultaneous dominating set on
perfect graphs, unless P=NP. Finally, we provide a 2-approximation algorithm
for finding a minimum simultaneous dominating set.
