How many zombies are needed to catch the survivor on toroidal grids?

DOI10.1016/J.TCS.2018.05.021MaRDI QIDQ2328860zbMATH OpenOpenAlexWikidataFDO

Authors Paweł Prałat

Publication date 16 October 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.09616

zbMATH Keywords

graphtoroidal grid

Mathematics Subject Classification ID

Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: In Zombies and Survivors, a set of zombies attempts to eat a lone survivor loose on a given graph. The zombies randomly choose their initial location, and during the course of the game, move directly toward the survivor. At each round, they move to the neighbouring vertex that minimizes the distance to the survivor; if there is more than one such vertex, then they choose one uniformly at random. The survivor attempts to escape from the zombies by moving to a neighbouring vertex or staying on his current vertex. The zombies win if eventually one of them eats the survivor by landing on their vertex; otherwise, the survivor wins. The zombie number of a graph is the minimum number of zombies needed to play such that the probability that they win is at least 1/2. This variant of the game was recently investigated for several graph families, such as cycles, hypercubes, incidence graphs of projective planes, and grids $P_{n}square{P}_n$. However, unfortunately, still very little is known for toroidal grids $C_{n}square{C}_n$: the zombie number of $C_{n}square{C}_n$ is at least $sqrtn/(omegalogn)$, where $omega=omega(n)$ is any function going to infinity as $noinfty$, and no upper bound is known except a trivial bound of $O(n^{2}logn)$. In this note, we provide an approach that gives an embarrassing bound of $O(n^2)$ but it is possible that (with more careful, deterministic, argument) it might actually give a bound of $O(n^{3/2})$. On the other hand, by analyzing a specific strategy for the survivor, it seems that one could slightly improve the lower bound to $sqrtn/omega$. In any case, we are far away from understanding this intriguing question. Your help is needed!

Review text

An important class of graphs is used for the mathematical modeling of the toroidal grids with significant applications.

Recommendations

• A probabilistic version of the game of zombies and survivors on graphs
• A deterministic version of the game of zombies and survivors on graphs
• Zombie number of the Cartesian product of graphs
• A note on deterministic zombies
• Comparing the power of cops to zombies in pursuit-evasion games

Cites work

• A deterministic version of the game of zombies and survivors on graphs
• A probabilistic version of the game of zombies and survivors on graphs

Cited in

(5)

• A note on deterministic zombies
• A deterministic version of the game of zombies and survivors on graphs
• A probabilistic version of the game of zombies and survivors on graphs
• scientific article; zbMATH DE number 1522929 (Why is no real title available?)
• Pursuit-evasion in graphs: zombies, lazy zombies and a survivor

This page was built for publication: How many zombies are needed to catch the survivor on toroidal grids?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2328860)