Predicting The Cop Number Using Machine Learning

Although the Maximum Clique Problem (MCP) has been extensively studied and features a rich ecosystem of exact solvers, empirical evidence shows that solver performance varies substantially across graph families. Consequently, selecting an appropriate algorithm for a given instance remains an open and practically important challenge that has received little systematic attention. We address this gap by developing an instance-aware selection framework that systematically combines global statistical descriptors with learned topological representations. We construct a comprehensive benchmark by evaluating four state-of-the-art exact solvers on a diverse collection of graph instances and deriving both global statistical and local structural features. An evaluation of conventional classifiers establishes Random Forest as a strong baseline and reveals that connectivity and topological features are key predictors of performance. Motivated by these observations, we introduce a dual-channel architecture that jointly leverages a Graph Attention Network for capturing local neighborhood patterns and a Multilayer Perceptron for modeling global statistical features. Extensive experiments show that the proposed dual-channel model consistently surpasses classical baselines and the single-best solver, achieving 90.43% test accuracy. These findings demonstrate the value of integrating local topological encoding with global statistical cues for combinatorial algorithm selection. Code and models are available at: https://anonymous.4open.science/r/GAT-MLP-7E5F.

This work identifies the dominance regions for discrete, simultaneous-move pursuit-evasion games on graphs. Existing geometric approaches provide efficient characterizations of winning regions, but typically provide only sufficient conditions and rely on open-loop strategies. To address these challenges, we develop a set-based dynamic programming approach to characterize the pursuer's winning and losing regions, providing necessary and sufficient winning conditions under worst-case behavior. The reachability analysis admits a set-chasing interpretation, allowing translation of dominance sets to feedback strategies that adapt to the players' positions in real time. For states where neither player can guarantee victory, we introduce an instantaneous matrix-game formulation and establish upper and lower bounds on the pursuer's winning probability. Simulation results validate the correctness of the dominance-region characterization and the proposed bounds.

Existing continuous-time graph learning methods rely heavily on complex neural architectures to encode ever-expanding interaction histories. However, the future conditional distribution induced by complex histories can often be characterized by a low-dimensional predictive state manifold, implying that only a few predictive degrees of freedom are essential for future interactions. We therefore argue that continuous-time graph learning should identify low-dimensional states sufficient for future prediction rather than reconstruct the full history. To make this perspective measurable, we define and independently estimate the intrinsic predictive dimension, which quantifies the effective predictive degrees of freedom required by a given task. Specifically, we remove the history-independent marginal from the history-conditioned future distribution, decompose the resulting predictive residual operator, and estimate the minimum effective rank needed to preserve the predictive power of the full history. Experiments across datasets show that model performance saturation is largely determined by the intrinsic predictive dimension. Based on this finding, we propose PreDyG, a lightweight model whose capacity is matched to the intrinsic predictive dimension. PreDyG achieves superior predictive performance with only 0.07% of the parameters of a representative complex baseline.