Given an unweighted, undirected graph, a dominating set $S$ is a set of nodes such that every node is in $S$ or adjacent to a node in $S$.
The dominating set problem is NP-hard, but I am considering a new variation. Given $k$, the size of the minimum dominating set, I need to find a set of nodes $T$ of size at most $k$ such that there exists a minimum dominating set $S$ in the graph which is dominated by $T$. That is, every any node in $S$ should be in $T$ or adjacent to a node in $T$.
My attempt: The following is an algorithm I came up with that I have not proven or found a counterexample for. At the start, all nodes are unmarked.
1) Pick an unmarked node $v$ as a center and mark everything within 2 hops of $v$. EDIT: Instead of picking an arbitrary unmarked node in this step, select the node that would cause the least number of nodes to be marked.
2) Repeat step 1 until all nodes are marked. (Note, this will never place more than $k$ centers)
3) If we have picked less than $k$ centers, keep placing centers on undominated nodes until we have placed $k$ centers.
I have proved that the above algorithm finds a set of centers which dominates a minimum dominating set, under the condition that we don't place any centers in step 3. That is, the algorithm works if steps 1 and 2 manage to place exactly $k$ centers.
Any ideas for whether this algorithm works or a counterexample?