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.