A faster algorithm for cops and robbers

DOI10.1016/J.DAM.2022.05.019MaRDI QIDQ2166209zbMATH OpenOpenAlexWikidataFDO

Authors Jan Petr, Julien Portier, Leo Versteegen

Publication date 24 August 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

algorithmcomplexitycops and robbers

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43)

Abstract: We present an algorithm of time complexity $O(k{n}^{k+2})$ deciding whether a graph $G$ on $n$ vertices is $k$-copwin. The fastest algorithm thus far had time complexity $O(n^{2k+2})$.

Recommendations

• Pursuing a fast robber on a graph
• The complexity of pursuit on a graph
• The capture time of a graph
• A note on \(k\)-cop, \(l\)-robber games on graphs
• Bounds on the length of a game of cops and robbers

Cites work

• A deterministic version of the game of zombies and survivors on graphs
• A game of cops and robbers
• Characterizations of k-copwin graphs
• Cops and robbers in graphs with large girth and Cayley graphs
• Cops and robbers is EXPTIME-complete
• Fine-grained Lower Bounds on Cops and Robbers
• On Meyniel's conjecture of the cop number
• Vertex-to-vertex pursuit in a graph

Cited in

(7)

• Connected Search for a Lazy Robber
• Connected search for a lazy robber
• Cops \& robber on periodic temporal graphs: characterization and improved bounds
• Cops and robbers on multi-layer graphs
• Cops \& Robber on periodic temporal graphs
• On the cop number of string graphs
• Cops and attacking robbers with cycle constraints

This page was built for publication: A faster algorithm for cops and robbers

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