NPBench

Curated benchmarks for NP-hard combinatorial optimization

Classic DIMACS benchmarks, modern challenge datasets, known solutions, provenance, and machine-readable metadata for classical and modern NP-hard graph/combinatorial optimization problems.

Website: https://dynaroars.github.io/npbench/ (legacy pages; a new generated search UI is in progress, see below)

What this is

NPBench preserves and indexes benchmark instances for problems including:

• Graph Coloring (and generalizations: fixed-set coloring, bandwidth coloring, multicoloring)
• Maximum Clique
• Maximum Independent Set
• Minimum Vertex Cover
• Degree-Constrained Spanning Tree

Its historical roots are the Second DIMACS Implementation Challenge (1992-93) and Michael Trick's COLOR02/03/04 collections, extended over the years with BHOSLIB/FRB instances and other supplementary sets. Some of the collections NPBench hosts have already outlived their original web homes (DIMACS/Trick/BHOSLIB hosts have gone dead and come back at different addresses more than once); part of NPBench's job is simply not letting that material disappear.

NPBench is being modernized (see TODO.md for the in-progress plan) into a structured, searchable, verifiable archive rather than a set of hand-maintained HTML/org tables. This is in progress — some of what's below describes where the project is headed, not only where it is today.

By the numbers (current snapshot)

• ~912 files (~615 MB) under instances/, hashed and inventoried in catalog/inventory.json
• 1164 instances in the canonical catalog (catalog/instances.json), across 14 collections, 142 families, and 8 first-class problems (graph coloring + generalizations, maximum clique, maximum independent set, minimum vertex cover, degree-constrained spanning tree)

Repository layout

instances/          Original benchmark files (immutable archival bytes)
catalog/            Machine-readable catalog: instances/collections/families/problems.json
scripts/            Inventory, parsing, audit, catalog-build, and validation scripts
npbench/, bin/      Python API + CLI over the catalog
reports/            Human-readable audit/scouting/reconciliation reports
search/             Prototype static client-side search UI (not yet the deployed site)
docs/, *.org, *.html   Legacy hand-maintained pages (being superseded by the catalog)

Machine-readable metadata

Everything under catalog/ is generated, not hand-edited:

catalog/inventory.json          every file: path, size, SHA-256
catalog/current-instances.json  per-file structural audit (parsed V/E, issues)
catalog/instances.json          canonical per-instance record (id, problem,
                                 collection, family, graph stats, solution)
catalog/collections.json        one record per benchmark collection
catalog/families.json           one record per benchmark family
catalog/problems.json           one record per first-class problem
catalog/candidates.json         external collections scouted but not (yet)
                                 imported, each tagged HOST/INDEX/SKIP/INVESTIGATE

Regenerate the catalog from source with:

python3 scripts/inventory.py
python3 scripts/build_audit.py
python3 scripts/scrape_legacy_org.py
python3 scripts/build_catalog.py
python3 scripts/build_search_index.py
python3 scripts/build_pages.py
python3 scripts/build_api.py
python3 scripts/validate_catalog.py

Static JSON "API" endpoints (no server) live under search/api/: instances.json, collections.json, problems.json, families.json, and every instance individually at search/api/instance/<id>.json.

Command-line / programmatic access

A small CLI and Python API read directly from the catalog (not yet a published pip package — see TODO.md Task 34):

./bin/npbench search DSJC500
./bin/npbench search --problem maximum-clique --min-vertices 1000
./bin/npbench info <instance-id>
./bin/npbench download <instance-id> --to ./mygraph.col
./bin/npbench verify <instance-id> mysolution.sol --problem clique
./bin/npbench convert <instance-id> --to edgelist

import npbench
hits = npbench.search(problem="maximum-clique", min_vertices=1000)
inst = npbench.get("DSJC500.5")   # raises if the name is ambiguous
path = npbench.path(inst["id"])

scripts/verify_solution.py independently checks feasibility (not optimality) of a candidate clique/independent-set/vertex-cover/coloring solution against a hosted graph — it does not just trust a claimed value.

Search and permalink pages (prototype)

A dependency-free static search/filter UI over the catalog lives in search/ (see search/index.html), plus a generated, server-renderable permalink page for every instance/collection/problem/family (search/{instance,collection,problem,family}/<id>/index.html, search/sitemap.xml, search/robots.txt — Task 27-30/47). None of this is wired into the deployed dynaroars.github.io/npbench site yet. Try it locally:

python3 -m http.server 8000
# open http://localhost:8000/search/

Solution values

Where a legacy NPBench table had a solution value for an instance, it's carried forward under solution.legacy in catalog/instances.json — but it is not presented as a current, proven optimum. solution.status distinguishes historical-unverified, lower-bound-only-historical, unknown (legacy table said "?"), and not_researched. Re-verifying these against current literature is future work (see TODO.md §38); please don't treat an old table value as settled.

Provenance and preservation policy

• Original benchmark bytes are immutable archival objects. NPBench does not silently "fix" malformed historical files; issues (self-loops, duplicate edges, header/content mismatches, etc.) are recorded as metadata instead — see reports/audit.md.
• Where NPBench merely indexes an external, actively-maintained collection (e.g. PACE challenges) rather than hosting a copy, that is recorded explicitly (HOST vs INDEX vs SKIP in catalog/candidates.json).
• NPBench's own code/website (LICENSE, MIT) is licensed separately from the benchmark data it preserves. Licensing on individual benchmark files is often unclear or undocumented upstream; the MIT license does not extend to anything under instances/ — see PROVENANCE.md for the per-collection licensing status.

Contributing

See CONTRIBUTING.md. Corrections to metadata, proposals for missing benchmark collections, improved bounds/optima with citations, and solution certificates are all welcome — please don't submit arbitrary generated benchmark dumps.

Citation

See CITATION.cff for citing NPBench itself. Please also cite the original source of any specific benchmark you use — see the citation field on that instance's collection in catalog/collections.json (also shown on that collection's page under search/collection/<id>/), where verified. Not every collection has one yet.

Contact

Maintained by ThanhVu (Vu) Nguyen and Thang Bui.