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 , 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.
Type de document :
Communication dans un congrès
28th International Symposium on Algorithms and Computation (ISAAC 2017), 2017, Phuket, Thailand. <10.4230/LIPIcs>
Liste complète des métadonnées


https://hal.inria.fr/hal-01582091
Contributeur : Nicolas Nisse <>
Soumis le : mardi 5 septembre 2017 - 15:20:36
Dernière modification le : mercredi 13 septembre 2017 - 01:11:46

Fichier

ISAAC2017_revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

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>

Partager

Métriques

Consultations de
la notice

85

Téléchargements du document

23