Paperlane

no. 16 · Tuesday 17 November 2026

Branch-and-Cut for Maximum $k$-Independent Sets with Spectral Bounds

Aida Abiad, Julian Golak and Arne Schulz

math.OC

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
pdf ↗ page arXiv:2611.20957 ↗