Branch-and-Cut for Maximum $k$-Independent Sets with Spectral Bounds
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.
Authors
- J. Golak (ORCID: https://orcid.org/0000-0002-5210-6910)
- Arne Schulz (ORCID: https://orcid.org/0000-0002-3088-2820)
- Aida Abiad (ORCID: https://orcid.org/0000-0003-4003-4291)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-16
- DOI
- https://doi.org/10.48550/arxiv.2611.20957
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint