Simultaneously Dominating all Spanning Trees of a Graph

Sebastian S. Johann, Sven O. Krumke, Manuel Streicher

A subset of the vertices of a graph is a simultaneous dominating set for spanning trees if it is a dominating set in every spanning tree of the graph. We consider the problem of finding a minimum size simultaneous dominating set for spanning trees. We show that the decision version of this problem is NP-complete by pointing out its close relation to the vertex cover problem. We present an exact algorithm to solve this problem and show how to solve it in polynomial time on some graph classes like bipartite or chordal graphs. Moreover, we derive a $2$-approximation algorithm for this problem.

Knowledge Graph



Sign up or login to leave a comment