Study of a combinatorial game in graphs through Linear Programming

In the Spy Game played on a graph G, a single spy travels the vertices of G at speed s,while multiple slow guards strive to have, at all times, one of them within distance d of thatspy. In order to determine the smallest number of guards necessary for this task, we analyzethe game through a Linear Programming formulation and the fractional strategies it yields forthe guards. We then show the equivalence of fractional and integral strategies in trees. Thisallows us to design a polynomial-time algorithm for computing an optimal strategy in this classof graphs. Using duality in Linear Programming, we also provide non-trivial bounds on thefractional guard-number of grids and torus which gives a lower bound for the integral guard numberin these graphs. We believe that the approach using fractional relaxation and LinearProgramming is promising to obtain new results in the field of combinatorial games