A cops and robber game and the meeting time of synchronous directed walks - Télécom SudParis Access content directly
Journal Articles Networks Year : 2024

A cops and robber game and the meeting time of synchronous directed walks

Abstract

In a previous work, the authors showed that} the maximum number of infinitely long synchronous directed walks that never meet is equal to the dimension $d$ of the no-meet matroid, namely the largest order of a collection of vertex-disjoint cycles. Given \rev{$w > d$} , we want to compute the meeting time {of \rev{$w$} walks}: the first time step \rev{$t_w$} such that, given any set of \rev{$w$} walks, at least two of them must meet no later than \rev{$t_w$}. We precisely prove that the meeting time is at most \rev{$n - w+2$}, where $n$ is the number of vertices. A connection is established with a cops and robber game on directed graphs with helicopter cops and an invisible slow robber. The meeting time of \rev{$w$} walks equals the capture time in this game, when at most \rev{$w-1$} capture attempts are allowed. While this capture time can be computed in polynomial time, we show that it is NP-hard to compute the minimum number of cops $h$ needed to catch the robber. More insights are also given on the number $h$ and its relation to pathwidth and other graph parameters. Finally we analyze these game measures on digraph tensor products.
Fichier principal
Vignette du fichier
Some_pursuit_evasion_games_on_digraphs-4.pdf (189.45 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-04607550 , version 1 (10-06-2024)

Identifiers

Cite

Walid Ben-Ameur, Walid Ben-Ameur, Alessandro Maddaloni. A cops and robber game and the meeting time of synchronous directed walks. Networks, 2024, ⟨10.1002/net.22234⟩. ⟨hal-04607550⟩
9 View
2 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More