A faster algorithm for Cops and Robbers

Jan Petr, Julien Portier, Leo Versteegen

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})…