Study of a combinatorial game in graphs through Linear Programming

Nathann Cohen 1 Fionn Mc Inerney 2 Nicolas Nisse 2 Stéphane Pérennes 2
1 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
LRI - Laboratoire de Recherche en Informatique
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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 that spy. In order to determine the smallest number of guards necessary for this task, we analyze the game through a Linear Programming formulation and the fractional strategies it yields for the guards. We then show the equivalence of fractional and integral strategies in trees. This allows us to design a polynomial-time algorithm for computing an optimal strategy in this class of graphs. Using duality in Linear Programming, we also provide non-trivial bounds on the fractional guard-number of grids and torus. We believe that the approach using fractional relaxation and Linear Programming is promising to obtain new results in the field of combinatorial games.
Document type :
Conference papers
Complete list of metadatas

Cited literature [2 references]  Display  Hide  Download
Contributor : Nicolas Nisse <>
Submitted on : Tuesday, September 5, 2017 - 3:20:36 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM


Files produced by the author(s)



Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes. Study of a combinatorial game in graphs through Linear Programming. 28th International Symposium on Algorithms and Computation (ISAAC 2017), 2017, Phuket, Thailand. ⟨10.4230/LIPIcs⟩. ⟨hal-01582091⟩



Record views


Files downloads