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

CREATORSemih Cantürk, Thomas Sabourin, Frederik Wenkel, Michael Perlmutter, Guy Wolf
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51859
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.02462

Browse the full library · About the Tower of Babel