![[2602.16600] Predicting The Cop Number Using Machine Learning](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.16600] Predicting The Cop Number Using Machine Learning
Summary
This article explores the use of machine learning to predict the cop number in graph theory, demonstrating the effectiveness of classical models and graph neural networks in this computationally challenging task.
Why It Matters
Understanding the cop number is crucial in graph theory and has applications in network security and game theory. This research highlights how machine learning can provide scalable solutions to complex problems, enhancing existing algorithms and making them more accessible.
Key Takeaways
- Machine learning can effectively predict the cop number of graphs.
- Tree-based models show high accuracy despite class imbalance.
- Graph neural networks achieve comparable results without extensive feature engineering.
- Key predictive features include node connectivity and clustering.
- Machine learning can complement traditional algorithms for scalability.
Computer Science > Machine Learning arXiv:2602.16600 (cs) [Submitted on 18 Feb 2026] Title:Predicting The Cop Number Using Machine Learning Authors:Meagan Mann, Christian Muise, Erin Meger View a PDF of the paper titled Predicting The Cop Number Using Machine Learning, by Meagan Mann and 2 other authors View PDF HTML (experimental) Abstract: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 para...