Predicting The Cop Number Using Machine Learning
This work addresses a specific problem in graph theory for researchers by providing scalable approximations to complement existing algorithms, though it is incremental as it applies known machine learning methods to a new domain.
The paper tackled the problem of predicting the cop number of graphs, a computationally difficult pursuit-evasion game parameter, using machine learning methods, and found that tree-based models and graph neural networks achieve high accuracy in prediction, with interpretability analysis identifying key structural features like node connectivity and clustering.
Cops and Robbers is a pursuit evasion game played on a graph, first introduced independently by Quilliot \cite{quilliot1978jeux} and Nowakowski and Winkler \cite{NOWAKOWSKI1983235} over four decades ago. A main interest in recent the literature is identifying the cop number of graph families. The cop number of a graph, $c(G)$, is defined as the minimum number of cops required to guarantee capture of the robber. Determining the cop number is computationally difficult and exact algorithms for this are typically restricted to small graph families. This paper investigates whether classical machine learning methods and graph neural networks can accurately predict a graph's cop number from its structural properties and identify which properties most strongly influence this prediction. Of the classical machine learning models, tree-based models achieve high accuracy in prediction despite class imbalance, whereas graph neural networks achieve comparable results without explicit feature engineering. The interpretability analysis shows that the most predictive features are related to node connectivity, clustering, clique structure, and width parameters, which aligns with known theoretical results. Our findings suggest that machine learning approaches can be used in complement with existing cop number algorithms by offering scalable approximations where computation is infeasible.