← All benchmarks

Maximum Independent Set

Best-known set sizes matched on most graphs — in about a second.

What we compare

On the QOBLIB independent-set benchmark (50 graphs) we compare the set size Quicopt finds against the QOBLIB reference (38 proven-optimal, 12 best-known). 100% means the reference size was matched.

Related problem class

QUBO / Ising
8090.5101instance (sorted)% of best-known
Solution quality on the 50 QOBLIB independent-set graphs: Quicopt’s set size as a percentage of the best-known value, one point per instance, sorted. The median is 100% — 30 of 50 graphs are solved to the reference size.

System setup

Quicopt v0.1, the same run reported on two back-ends: an NVIDIA A100 80GB GPU and a single core of an AMD EPYC-Rome CPU. Most graphs finish in roughly a second; even the largest stay within seconds on the GPU.

The problem, in depth

A maximum independent set is the largest possible set of vertices no two of which share an edge — a classic NP-hard problem underlying scheduling, coding theory and network design. Like Max-Cut it maps to a QUBO/Ising energy, the native form for quantum and quantum-inspired solvers.

The QOBLIB suite mixes structured combinatorial graphs (DIMACS, Steiner-tree, coding) with real social and biological networks, from 17 to 4,000 nodes and up to about four million edges.

How the benchmark is run

Quicopt minimizes the independent-set Ising energy and the resulting set size is recorded for each graph. Against the QOBLIB reference all 50 instances are graded: median 100%, range 82.6–100.0% of best-known.

Notably, a single CPU core is competitive with the A100 on most graphs; per instance the faster back-end is reported. As with every family here, the full per-instance results are public and reproducible.

Reference values are the QOBLIB solutions (third-party), not Quicopt output. Full per-instance data: quicoptbenchmarks · QOBLIB dataset