ABSTRACT We investigate a cops and robber game on directed graphs, where the robber moves along the arcs of the graph, whereas the cops can select any position at each time step. Our main focus is on the cop number: the minimum number of cops required to guarantee the capture of the robber. We prove that deciding whether the cop number of a digraph is equal to 1 is NP‐hard, whereas this is decidable in polynomial time for tournaments. Furthermore, we show that computing the cop number for general digraphs is fixed parameter tractable when parameterized by a generalization of vertex cover. However, for tournaments, tractability is achieved with respect to the minimum size of a feedback vertex set. Among our findings, we prove that the cop number of a digraph is equal to that of its reverse digraph, and we draw connections to the matrix mortality problem.

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 of the no‐meet matroid, namely the largest order of a collection of vertex‐disjoint cycles. Given , we want to compute the meeting time of walks: the first time step such that, given any set of walks, at least two of them must meet no later than . We precisely prove that the meeting time is at most , where 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 walks equals the capture time in this game, when at most 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 needed to catch the robber. More insights are also given on the number and its relation to pathwidth and other graph parameters. Finally we analyze these game measures on digraph tensor products.