Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization

Abstract:Neural solvers provide fast solutions to graph combinatorial optimization problems, but training alone does not guarantee solution quality. Exact methods guarantee optimality but can be prohibitively expensive. We propose Neural Fixed-Parameter Tractable (N-FPT), a neural-model-agnostic framework that uses parameterized algorithms to improve neural solutions without retraining and guide learning. It restricts neural advice to a treewidth modulator and completes the bounded-treewidth remainder exactly. It returns and certifies the best achievable solution under any valid advice, improving the neural solution whenever a better compatible completion exists. We prove this guarantee and global optimality under perfect advice. Its incremental-confidence N-FPT (NIC-FPT) and randomized-deferral N-FPT (NRD-FPT) variants consolidate neural advice. Beyond inference, N-FPT feedback becomes available as neural decisions make exact completion tractable. From that state onward, it supplies what final solution rewards lack: the first decision that rules out every optimal completion and alternatives that preserve one. One exact computation supplies reusable guidance for continuations from that state, even when neural samples miss its optimum. Experiments across graph combinatorial optimization problems demonstrate solution-quality gains with different neural models and robustness to graph-size and distribution shifts. The learned completion model reaches optimal completions more often than reinforcement learning (RL) alone, without an exact solver at inference. N-FPT thus uses graph structure to improve neural solutions and guide learning toward optimal completion.

Machine Learning (cs.LG); Machine Learning (stat.ML)

arXiv:2511.19573 [cs.LG]

(or arXiv:2511.19573v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2511.19573 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.