Maximum Independent Set

Unweighted MIS on Hard Graphs

Binary QUBO graph-theory NP-hard benchmark-classic

Instances 50

Optimally solved 39 / 50

Variable range 17–4,000

Objective maximize

Overview

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.

Problem Description

Given a graph $G=(V,E)$, find an independent set $I \subseteq V$ of maximum cardinality.

Definition: A set $I \subseteq V$ is independent (or stable ) if no two vertices in $I$ are adjacent, i.e., there does not exist an edge $(u,v) \in E$ with $u, v \in I$.

Objective: Maximize $|I|$.

Performance

Runtime to reach best-known objective

Sorted instances vs total runtime. A point (x, y) means x instances were solved within y seconds. Solid line + filled circle = proven exact; dashed line + open diamond = heuristic. Lower-right is better.

Classical (50 · 2 exact, 48 heuristic) Quantum simulator (1 · heuristic) Quantum hardware (24 · heuristic)

Time-to-solution (TTS) to reach best-known objective

Same as the runtime cactus but uses the reported Time-to-Solution rather than total runtime. Solid = exact, dashed = heuristic.

Classical (42 · 28 exact, 14 heuristic) Quantum hardware (12 · heuristic)

Solution quality (performance profile)

Share of instances each group brings within a given optimality gap of the best-known objective. Higher is better; the value at “best” is the share solved exactly.

Classical (50) Quantum simulator (3) Quantum hardware (28)

Runtime scaling with instance size

Fastest feasible runtime (log scale) per instance versus Nodes — shows how each group scales.

Classical (50) Quantum simulator (3) Quantum hardware (28)

Submissions (16)

Method	Submitter	Type	Date	Instances
Quicopt	Tim Bode	Classical	2026-08-13	50
ParallelILS	Narendra N. Hegade	Classical	2026-08-06	50
HSQC	Narendra N. Hegade	Quantum HW	20260804	6
Parity_Twine	ParityQC Team	Quantum HW	2026-07-30	6
Aqarios	David Bucher	Quantum HW	2026-07-11	5
SA	Q-Bridge Team	Classical	2026-07-09	4
20260709_JIJ	Keisuke Sato, Hiromichi Matsuyama, Yuichiro Nakano, Kohji Nishimura, Yu Yamashiro	Quantum HW	2026-07-09	26
Qunova	Jeung Rac Lee	Quantum HW	20260630	5
QctrlSolver	Kara Maller	Quantum HW	2026-06-24	2
QAOA_AerMPS	Alejandro Montanez	Quantum sim	2026-06-11	1
Arvak	Daniel Hinderink	Quantum sim	2026-03-08	3
QAOA_ibm_boston	Alejandro Montanez	Quantum HW	2025-11-27	1
MIP	Maximilian Schicker	Classical	2025-07-15	50
Abs2	Maximilian Schicker	Classical	2025-07-15	50
Quicopt	Tim Bode	Classical	20250627	6
QAOA	Daniel Egger	Quantum HW	2025-01-15	2

Instances (50)

50 of 50

Name	Nodes	Edges	Best objective	Source	Status	Download
aves-sparrow-social	52	454	13	Reference solution	Optimal	↓ raw
brock200-1	200	14,834	6	Reference solution	Optimal	↓ raw
brock200-2	200	10,024	12	Reference solution	Optimal	↓ raw
brock200-3	200	12,048	9	Reference solution	Optimal	↓ raw
brock200-4	200	13,089	8	Reference solution	Optimal	↓ raw
brock400-1	400	20,077	27	Reference solution	Optimal	↓ raw
brock800-1	800	112,095	23	Reference solution	Optimal	↓ raw
C125-9	125	787	34	Reference solution	Optimal	↓ raw
C500-9	500	12,418	57	Reference solution	Best known	↓ raw
C4000-5	4,000	3,997,732	18	Reference solution	Best known	↓ raw
c-fat200-1	200	1,534	18	Reference solution	Optimal	↓ raw
chesapeake	39	170	17	Reference solution	Optimal	↓ raw
es60fst01	123	159	60	Reference solution	Optimal	↓ raw
es60fst02	186	280	88	Reference solution	Optimal	↓ raw
es60fst03	113	142	55	Reference solution	Optimal	↓ raw
es60fst04	162	238	78	Reference solution	Optimal	↓ raw
farm	17	39	10	Reference solution	Optimal	↓ raw
football	35	118	16	Reference solution	Optimal	↓ raw
frb45-21-3	945	58,245	45	Reference solution	Optimal	↓ raw
frb50-23-3	1,150	81,068	50	Reference solution	Optimal	↓ raw
frb53-24-1	1,272	94,227	53	Reference solution	Best known	↓ raw
frb59-26-2	1,534	126,163	58	Reference solution	Best known	↓ raw
frb100-40	4,000	572,774	96	Reference solution	Best known	↓ raw
gen200_p0-9_44	200	1,990	44	Reference solution	Optimal	↓ raw
hamming6-2	64	1,824	2	Reference solution	Optimal	↓ raw
hamming6-4	64	704	12	Reference solution	Optimal	↓ raw
hamming10-4	1,024	89,600	40	Reference solution	Best known	↓ raw
ibm32	32	90	13	Reference solution	Optimal	↓ raw
insecta-ant-colony1-day38	56	1,134	6	Reference solution	Optimal	↓ raw
insecta-ant-colony3-day09	160	8,883	9	Reference solution	Optimal	↓ raw
johnson8-2-4	28	210	7	Reference solution	Optimal	↓ raw
johnson8-4-4	70	1,855	5	Reference solution	Optimal	↓ raw
johnson16-2-4	120	5,460	15	Reference solution	Optimal	↓ raw
karate	34	78	20	Reference solution	Optimal	↓ raw
keller4	171	5,100	11	Reference solution	Optimal	↓ raw
keller6	3,361	1,026,582	59	Reference solution	Best known	↓ raw
mammalia-kangaroo-interactions	17	91	4	Reference solution	Optimal	↓ raw
MANN-a9	45	918	3	Reference solution	Optimal	↓ raw
p_hat1500-1	1,500	839,327	12	Reference solution	Optimal	↓ raw
p_hat1500-3	1,500	277,006	94	Reference solution	Optimal	↓ raw
R_500_005_1	500	6,256	91	Reference solution	Best known	↓ raw
R_1000_005_1	1,000	24,670	117	Reference solution	Best known	↓ raw
sloane_1dc_64	64	543	10	Reference solution	Optimal	↓ raw
sloane_1dc_128	128	1,471	16	Reference solution	Optimal	↓ raw
sloane_1zc_128	128	1,120	18	Reference solution	Optimal	↓ raw
sloane_2dc_128	128	5,173	5	Reference solution	Optimal	↓ raw
socfb-haverford76	1,446	59,589	282	Reference solution	Optimal	↓ raw
socfb-trinity100	2,613	111,996	499	Reference solution	Best known	↓ raw
sorrell4	2,048	504,451	24	Reference solution	Optimal	↓ raw
sorrell7	2,048	39,424	198	Reference solution	Best known	↓ raw

View on GitHub ↗ View Leaderboard Browse All Instances