Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?
Semih Cantürk, Thomas Sabourin, Frederik Wenkel, Michael Perlmutter, Guy Wolf · 2026
Read Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization? by Semih Cantürk, Thomas Sabourin, Frederik Wenkel, Michael Perlmutter, Guy Wolf (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-02462.txt.
Description
Semih Cantürk, Thomas Sabourin, Frederik Wenkel, and colleagues test transfer across hard graph problems in this 2026 paper. Neural solvers learn to tackle combinatorial problems like clique and cover finding. Training one solver per problem is wasteful if skills overlap. The authors ask whether reducibility, the classic map between problems, can guide transfer.
Their solver uses strong message passing with an energy-based unsupervised loss. Trained alone, it matches leading results on several problems. Pretraining strategies drawn from reduction theory then move skills between tasks. Leaving one task out, pretraining on the rest sped fine-tuning on it almost always. No harmful transfer appeared in that setting. Shared representations across graph problems look viable, a step toward foundation solvers.
Catalog record
| CREATOR | Semih Cantürk, Thomas Sabourin, Frederik Wenkel, Michael Perlmutter, Guy Wolf |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51859 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.02462