Alternative Names: Maximum Stable Set Problem, MISP
The Maximum Independent Set Problem is a fundamental graph optimization problem with applications in scheduling, resource allocation, and network design. Despite its simple formulation, it is NP-hard and challenging even for moderately-sized graphs.
Given a graph
Definition: A set
Objective: Maximize
- instances/ - Graph instances in various formats
- models/ - Mathematical model formulations
- solutions/ - Optimal or best-known solutions
- check/ - Solution verification tools
- misc/ - Utility scripts and generators
- submissions/ - Community solution submissions
- Parekh et al. - Benchmarking Adiabatic Quantum Optimization for Complex Network Analysis - D-Wave experiments on Chimera graphs
- Morita & Nishimori - Mathematical Foundation of Quantum Annealing
- Gaar, Siebenhofer, Wiegele - An SDP-based approach for computing the stability number of a graph - D-Wave 2X experiments on random graphs
- Povh & Pucher - Advancing stable set problem solutions through quantum annealers - QUBO formulation on D-Wave
- Krpan, Povh, Pucher - Quantum computing and the stable set problem - QUBO with post-processing and partitioning methods
- Chapuis et al. - Finding Maximum Cliques on the D-Wave Quantum Annealer - Comparison with classical algorithms
-
Xiao, M., Nagamochi, H. (2013). Exact Algorithms for Maximum Independent Set. In: Cai, L., Cheng, S.W., Lam, T.W. (eds) Algorithms and Computation. ISAAC 2013. Lecture Notes in Computer Science, vol 8283. Springer, Berlin, Heidelberg.
-
Hoang, D.A. (2023). On the Complexity of Distance-d Independent Set Reconfiguration. In: Lin, C.C., Lin, B.M.T., Liotta, G. (eds) WALCOM: Algorithms and Computation. WALCOM 2023. Lecture Notes in Computer Science, vol 13973.