no. 16 · Tuesday 17 November 2026
Branch-and-Cut for Maximum $k$-Independent Sets with Spectral Bounds
Abstract
We develop a branch-and-cut method for finding maximum distance-independent sets in graphs. Our approach solves a sequence of fixed-size clique problems, combining graph reductions with combinatorial and spectral bounds. We give a compact formulation, derive strengthened inequalities, establish conditions for using spectral information, and evaluate them in a comprehensive computational study.
- fields
- Optimization and Control