Search papers, labs, and topics across Lattice.
This paper explores the use of classical machine learning methods and graph neural networks (GNNs) to predict the cop number of a graph, a computationally challenging problem in graph theory. The study aims to determine if these methods can accurately predict the cop number based on structural properties and identify the most influential properties. Results show that tree-based models achieve high accuracy despite class imbalance, while GNNs achieve comparable results without explicit feature engineering, and interpretability analysis reveals that node connectivity, clustering, clique structure, and width parameters are the most predictive features.
Machine learning can accurately predict a graph's cop number, offering a scalable approximation where exact computation is infeasible.
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.
