Document Open Access Logo

Study of a Combinatorial Game in Graphs Through Linear Programming

Authors Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.22.pdf
  • Filesize: 0.73 MB
  • 13 pages

Document Identifiers

Author Details

Nathann Cohen
Fionn Mc Inerney
Nicolas Nisse
Stéphane Pérennes

Cite As Get BibTex

Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, and Stéphane Pérennes. Study of a Combinatorial Game in Graphs Through Linear Programming. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.22

Abstract

In the Spy Game played on a graph G, a single spy travels the ertices 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 guardnumber 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.

Subject Classification

Keywords
  • Turn-by-turn games in graphs
  • Graph algorithms
  • Linear Programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Aigner and M. Fromme. A game of cops and robbers. Discrete Applied Mathematics, 8:1-12, 1984. Google Scholar
  2. P. Balister, S. Binski, B. Bollobás, and B. P. Narayanan. Catching a fast robber on the grid. CoRR, abs/1609.01002, 2016. URL: http://arxiv.org/abs/1609.01002.
  3. I. Beaton, S. Finbow, and J.A. MacDonald. Eternal domination numbers of 4× n grid graphs. J. Comb. Math. Comb. Comput., 85:33-48, 2013. Google Scholar
  4. A. Bonato, E. Chiniforooshan, and P. Pralat. Cops and robbers from a distance. Theor. Comput. Sci., 411(43):3834-3844, 2010. Google Scholar
  5. A. Bonato and R. J. Nowakowski. The game of Cops and Robbers on Graphs. American Math. Soc., 2011. Google Scholar
  6. J. A. Bondy and U. S. R. Murty. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, 2008. Google Scholar
  7. A. Burger, E. J. Cockayne, W. R. Gründlingh, C. M. Mynhardt, J. H. van Vuuren, and W. Winterbach. Infinite order domination in graphs. J. Comb. Math. Comb. Comput., 50:179-194, 2004. Google Scholar
  8. N. Cohen, M. Hilaire, N. A. Martins, N. Nisse, and S. Pérennes. Spy-game on graphs. In 8th International Conference on Fun with Algorithms, FUN 2016, pages 10:1-10:16, 2016. Google Scholar
  9. N. Cohen, F. Mc Inerney, N. Nisse, and S. Pérennes. Study of a combinatorial game in graphs through linear programming. Technical report, INRIA, 2017. URL: https://hal.archives-ouvertes.fr/hal-01462890.
  10. N. Cohen, N. A. Martins, F. Mc Inerney, N. Nisse, S. Pérennes, and R. Sampaio. Spy-game on graphs: complexity and simple topologies. Technical report, INRIA, 2017. URL: https://hal.archives-ouvertes.fr/hal-01463297.
  11. A. Z. Delaney and M. E. Messinger. Closing the gap: Eternal domination on 3× n grids. to appear in Contributions to Discrete Mathematics, 2015. Google Scholar
  12. F. V. Fomin, F. Giroire, A. Jean-Marie, D. Mazauric, and N. Nisse. To satisfy impatient web surfers is hard. In 6th Int. Conf. on Fun with Algorithms (FUN), volume 7288 of LNCS, pages 166-176, 2012. Google Scholar
  13. F. V. Fomin, P. A. Golovach, J. Kratochvíl, N. Nisse, and K. Suchan. Pursuing a fast robber on a graph. Theor. Comput. Sci., 411(7-9):1167-1181, 2010. Google Scholar
  14. F. Giroire, D. Mazauric, N. Nisse, S. Pérennes, and R. P. Soares. Connected surveillance game. In 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science. Springer, 2013. Google Scholar
  15. F. Giroire, N. Nisse, S. Pérennes, and R. P. Soares. Fractional combinatorial games. Technical report, INRIA, 2013. RR8371. URL: http://hal.inria.fr/hal-00865345.
  16. W. Goddard, S. M. Hedetniemi, and S. T. Hedetniemi. Eternal security in graphs. J. Comb. Math. Comb. Comput., 52:160-180, 2005. Google Scholar
  17. D. Gonçalves, A. Pinlou, M. Rao, and S. Thomassé. The domination number of grids. SIAM J. Discrete Math., 25(3):1443-1453, 2011. Google Scholar
  18. W. B. Kinnersley. Cops and robbers is exptime-complete. JCTB, 111:201-220, 2015. Google Scholar
  19. W. F. Klostermeyer and G. MacGillivray. Eternal dominating sets in graphs. J. Comb. Math. Comb. Comput., 68, 2009. Google Scholar
  20. I. Lamprou, R. Martin, and S. Schewe. Perpetually dominating large grids. CoRR, abs/1611.08204, 2016. URL: http://arxiv.org/abs/1611.08204.
  21. R. J. Nowakowski and P. Winkler. Vertex-to-vertex pursuit in a graph. Discrete Maths, 43:235-239, 1983. Google Scholar
  22. A. Quilliot. Problèmes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes. Doctorat d'état, Univ. Paris 4, 1983. Google Scholar
  23. B. S. W. Schröder. The copnumber of a graph is bounded by ⌊ 3/2 genus (g) ⌋ + 3. Categorical perspectives (Kent, OH, 1998), Trends in Mathematics, pages 243-263, 2001. Google Scholar
  24. A. Scott and B. Sudakov. A bound for the cops and robbers problem. SIAM J. Discrete Math., 25(3):1438-1442, 2011. Google Scholar
  25. C. M. van Bommel and M. F. van Bommel. Eternal domination numbers of 5× n grid graphs. J. Comb. Math. Comb. Comput., 97:83-102, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact