How to guard a graph against tree moves

• The problem of minimizing the number of guards required to protect a general graph against a robber moving along a general tree is considered.
• A greedy algorithm is designed to approximate the problem within a factor of O(logn).
• It is described how to extended the problem to the weighted case and to approximate it still within a factor of O(logn).

This paper shows that the optimization problem arising from the guarding game played between the cop and robber players on an undirected graph can be approximated in polynomial time within a factor of Θ(logn) when the robber moves along a tree.