Fast Robber in Planar Graphs

Nicolas Nisse 1 Karol Suchan 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization 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 {\it cops and robber game}, two players play alternately by moving their tokens along the edges of a graph. The first one plays with the {\it cops} and the second one with one {\it robber}. The cops aim at capturing the robber, while the robber tries to infinitely evade the cops. The main problem consists in minimizing the number of cops used to capture the robber in a graph. This minimum number is called the {\it cop-number} of the graph. If the cops and the robber have the same velocity, $3+\frac{3}{2}g$ cops are sufficient to capture one robber in any graph with genus $g$ (Schröder, 2001). In the particular case of a grid, $2$ cops are sufficient. %In this paper, w We investigate the game in which the robber is slightly faster than the cops. In this setting, we prove that the cop-number of planar graphs becomes unbounded. More precisely, we prove that $\Omega(\sqrt{\log n})$ cops are necessary to capture a fast robber in the $n \times n$ square-grid. This proof consists in designing an elegant evasion-strategy for the robber. Then, it is interesting to ask whether a high value of the cop-number of a planar graph $H$ is related to a large grid $G$ somehow contained in $H$. We prove that it is not the case when the notion of containment is related to the classical transformations of edge removal, vertex removal, and edge contraction. For instance, we prove that there are graphs with cop-number at most $2$ and that are subdivisions of arbitrary large grid. On the positive side, we prove that, if $H$ planar contains a large grid as an induced subgraph, then $H$ has large cop-number. Note that, generally, the cop-number of a graph $H$ is not closed by taking induced subgraphs $G$, even if $H$ is planar and $G$ is an distance-hereditary induced-subgraph.
Type de document :
Communication dans un congrès
International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2008, Durham, United Kingdom. 2008
Liste complète des métadonnées

https://hal.inria.fr/inria-00423451
Contributeur : Nicolas Nisse <>
Soumis le : samedi 10 octobre 2009 - 13:44:06
Dernière modification le : lundi 5 novembre 2018 - 15:36:03

Identifiants

  • HAL Id : inria-00423451, version 1

Citation

Nicolas Nisse, Karol Suchan. Fast Robber in Planar Graphs. International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2008, Durham, United Kingdom. 2008. 〈inria-00423451〉

Partager

Métriques

Consultations de la notice

246