Two Step Graph Protection Game

The two-step graph protection game is a two-player game played on an n-vertex graph G, where one player is the attacker and the second player is the defender. The defender has k guards which he places on some vertices of the graph at the beginning of the game. In each move, the attacker attacks an edge. The defender moves the guards in such a manner that each guard can move at most two steps (along two adjacent edges) without retracing his previous step and one of the guards must move along the attacked edge. If such a movement is not possible after a finite sequence of attacks, the attacker wins. If the defender is able to defend the graph for an infinite sequence of attacks, the defender wins. We define the minimum number of guards for which the defender has a winning strategy, as the two- step protection number of a graph G and denote it by tsn(G). We show that it is NP-hard to decide whether tsn(G)≤k for a given graph G and integer k and this problem is also W[2]-hard parameterized by k. We compute the tsn(G) for some graph classes, i.e., stars, paths, cycles, complete graphs, complete bipartite graphs and split graphs. We also generalize these results to a game where the guards can move for at most r steps (without retracing) where r is less than the diameter of the graph.