Reducing the Irreducible: Learning Reductions Beyond Exact Kernelization

Exact reductions simplify hard optimization problems while preserving optimality, but their structural requirements can leave difficult instances unchanged. We study this limitation for maximum independent set, a natural test case given the extensive exact-reduction literature for independent set and minimum vertex cover. We develop heuristic reductions that aim to retain optimal or near-optimal solutions while continuing to simplify instances on which exact rules stall. In reduce-then-solve, language-model-guided program search generates a fast reduction rule before an exact solver processes the remaining graph. Rules are selected jointly for graph shrinkage, solution quality, and runtime. These criteria reflect the practical purpose of reduction: remove computational work without losing too much solution value or spending more time than it saves. In reduce-as-solve, localized greedy trials guide successive decisions on the shrinking graph. Language-model-guided program search also generates a policy that uses cached trial solutions to decide which vertices to include or discard, requesting fresh trials only when the stored evidence is insufficient. The reduction rule and cache policy are generated offline on small synthetic graphs and applied to hard instances without further tuning or language-model calls. Experiments on the evaluated methods show that reduce-then-solve enables more reduced graphs to be solved to optimality within a fixed time budget while usually retaining most of the reference solution value. Reduce-as-solve achieves higher solution quality than the tested reduction-based and greedy baselines, while localization and caching reduce trial-evaluation costs. These results demonstrate the practical value of heuristic reduction when the tested exact rules provide no simplification.