BHOSLIB benchmark set

This is a selected set of instances form the Benchmarks with Hidden Optimum Solutions for Graph Problems.

Instanceω(G)Best knownNodesEdgesGraph degreesOptimum degrees
MedianIQRMedianIQR
frb30-15-1 30 30 45083 198369.0(17.00)377.0(25.25)
frb30-15-2 30 30 45083 151371.0(16.00)376.0(15.00)
frb30-15-3 30 30 45083 216370.5(19.75)374.0(17.50)
frb30-15-4 30 30 45083 194371.0(20.00)377.5(16.00)
frb30-15-5 30 30 45083 231370.5(22.00)374.5(18.75)
frb35-17-1 35 35 595148 859499.0(28.50)502.0(29.25)
frb35-17-2 35 35 595148 868500.0(23.00)507.0(20.00)
frb35-17-3 35 35 595148 784500.0(24.50)507.0(15.00)
frb35-17-4 35 35 595148 873501.0(22.00)506.5(26.00)
frb35-17-5 35 35 595148 572500.0(25.00)503.0(23.25)
frb40-19-1 40 40 760247 106652.0(31.50)662.0(33.00)
frb40-19-2 40 40 760247 157652.0(30.00)661.0(25.00)
frb40-19-3 40 40 760247 325649.0(24.00)656.0(27.00)
frb40-19-4 40 40 760246 815650.0(21.00)655.5(24.50)
frb40-19-5 40 40 760246 801652.0(25.00)653.5(22.50)
frb45-21-1 45 45 945386 854818.0(31.00)830.0(32.00)
frb45-21-2 45 45 945387 416822.0(28.00)828.0(28.00)
frb45-21-3 45 45 945387 795820.0(29.00)825.0(26.00)
frb45-21-4 45 45 945387 491820.0(33.00)837.0(37.00)
frb45-21-5 45 45 945387 461819.0(24.00)825.0(23.00)
frb50-23-1 50 50 1 150580 6031 011.0(36.00)1 019.0(35.50)
frb50-23-2 50 50 1 150579 8241 009.0(29.00)1 017.0(32.00)
frb50-23-3 50 50 1 150579 6071 009.5(26.00)1 016.0(26.50)
frb50-23-4 50 50 1 150580 4171 011.0(35.00)1 018.5(36.50)
frb50-23-5 50 50 1 150580 6401 011.0(40.00)1 019.5(35.75)
frb53-24-1 53 53 1 272714 1291 124.0(37.00)1 132.0(38.00)
frb53-24-2 53 53 1 272714 0671 124.5(35.00)1 129.5(37.00)
frb53-24-3 53 53 1 272714 2291 124.0(32.00)1 132.0(35.00)
frb53-24-4 53 53 1 272714 0481 123.0(35.00)1 136.0(35.50)
frb53-24-5 53 53 1 272714 1301 122.0(31.00)1 126.0(28.00)
frb59-26-1 59 59 1 5341 049 2561 369.5(33.00)1 371.5(28.75)
frb59-26-2 59 59 1 5341 049 6481 374.0(41.75)1 381.0(40.50)
frb59-26-3 59 59 1 5341 049 7291 368.0(40.00)1 377.0(38.00)
frb59-26-4 59 59 1 5341 048 8001 370.0(38.00)1 379.5(39.00)
frb59-26-5 59 59 1 5341 049 8291 368.0(44.00)1 384.0(52.00)
frb100-40 100 98 4 0007 425 2263 717.0(70.00)3 722.0(67.75)

The instances in DIMACS format can be downloaded from the BHOSLIB web site, or directly from here. Archives containing the whole dataset and the selected instances are available below.

Instance families and generators

The instances have been generated by transforming forced satisfiable SAT benchmarks of Model RB. More details are available on the BHOSLIB web site.

Instances

All solutions have been found with the MPI version of CLS-MC by Pullan et al.. If you have found other cliques or improved the best known solution, please let me know, so that I can update this page.

frb30-15-1
Graph with 450 nodes, 83 198 edges, and ω(G) = 30. Best-known solutions have size 30.
Available in DIMACS ascii format, or DIMACS binary format.
frb30-15-2
Graph with 450 nodes, 83 151 edges, and ω(G) = 30. Best-known solutions have size 30.
Available in DIMACS ascii format, or DIMACS binary format.
frb30-15-3
Graph with 450 nodes, 83 216 edges, and ω(G) = 30. Best-known solutions have size 30.
Available in DIMACS ascii format, or DIMACS binary format.
frb30-15-4
Graph with 450 nodes, 83 194 edges, and ω(G) = 30. Best-known solutions have size 30.
Available in DIMACS ascii format, or DIMACS binary format.
frb30-15-5
Graph with 450 nodes, 83 231 edges, and ω(G) = 30. Best-known solutions have size 30.
Available in DIMACS ascii format, or DIMACS binary format.
frb35-17-1
Graph with 595 nodes, 148 859 edges, and ω(G) = 35. Best-known solutions have size 35.
Available in DIMACS ascii format, or DIMACS binary format.
frb35-17-2
Graph with 595 nodes, 148 868 edges, and ω(G) = 35. Best-known solutions have size 35.
Available in DIMACS ascii format, or DIMACS binary format.
frb35-17-3
Graph with 595 nodes, 148 784 edges, and ω(G) = 35. Best-known solutions have size 35.
Available in DIMACS ascii format, or DIMACS binary format.
frb35-17-4
Graph with 595 nodes, 148 873 edges, and ω(G) = 35. Best-known solutions have size 35.
Available in DIMACS ascii format, or DIMACS binary format.
frb35-17-5
Graph with 595 nodes, 148 572 edges, and ω(G) = 35. Best-known solutions have size 35.
Available in DIMACS ascii format, or DIMACS binary format.
frb40-19-1
Graph with 760 nodes, 247 106 edges, and ω(G) = 40. Best-known solutions have size 40.
Available in DIMACS ascii format, or DIMACS binary format.
frb40-19-2
Graph with 760 nodes, 247 157 edges, and ω(G) = 40. Best-known solutions have size 40.
Available in DIMACS ascii format, or DIMACS binary format.
frb40-19-3
Graph with 760 nodes, 247 325 edges, and ω(G) = 40. Best-known solutions have size 40.
Available in DIMACS ascii format, or DIMACS binary format.
frb40-19-4
Graph with 760 nodes, 246 815 edges, and ω(G) = 40. Best-known solutions have size 40.
Available in DIMACS ascii format, or DIMACS binary format.
frb40-19-5
Graph with 760 nodes, 246 801 edges, and ω(G) = 40. Best-known solutions have size 40.
Available in DIMACS ascii format, or DIMACS binary format.
frb45-21-1
Graph with 945 nodes, 386 854 edges, and ω(G) = 45. Best-known solutions have size 45.
Available in DIMACS ascii format, or DIMACS binary format.
frb45-21-2
Graph with 945 nodes, 387 416 edges, and ω(G) = 45. Best-known solutions have size 45.
Available in DIMACS ascii format, or DIMACS binary format.
frb45-21-3
Graph with 945 nodes, 387 795 edges, and ω(G) = 45. Best-known solutions have size 45.
Available in DIMACS ascii format, or DIMACS binary format.
frb45-21-4
Graph with 945 nodes, 387 491 edges, and ω(G) = 45. Best-known solutions have size 45.
Available in DIMACS ascii format, or DIMACS binary format.
frb45-21-5
Graph with 945 nodes, 387 461 edges, and ω(G) = 45. Best-known solutions have size 45.
Available in DIMACS ascii format, or DIMACS binary format.
frb50-23-1
Graph with 1 150 nodes, 580 603 edges, and ω(G) = 50. Best-known solutions have size 50.
Available in DIMACS ascii format, or DIMACS binary format.
frb50-23-2
Graph with 1 150 nodes, 579 824 edges, and ω(G) = 50. Best-known solutions have size 50.
Available in DIMACS ascii format, or DIMACS binary format.
frb50-23-3
Graph with 1 150 nodes, 579 607 edges, and ω(G) = 50. Best-known solutions have size 50.
Available in DIMACS ascii format, or DIMACS binary format.
frb50-23-4
Graph with 1 150 nodes, 580 417 edges, and ω(G) = 50. Best-known solutions have size 50.
Available in DIMACS ascii format, or DIMACS binary format.
frb50-23-5
Graph with 1 150 nodes, 580 640 edges, and ω(G) = 50. Best-known solutions have size 50.
Available in DIMACS ascii format, or DIMACS binary format.
frb53-24-1
Graph with 1 272 nodes, 714 129 edges, and ω(G) = 53. Best-known solutions have size 53.
Available in DIMACS ascii format, or DIMACS binary format.
frb53-24-2
Graph with 1 272 nodes, 714 067 edges, and ω(G) = 53. Best-known solutions have size 53.
Available in DIMACS ascii format, or DIMACS binary format.
frb53-24-3
Graph with 1 272 nodes, 714 229 edges, and ω(G) = 53. Best-known solutions have size 53.
Available in DIMACS ascii format, or DIMACS binary format.
frb53-24-4
Graph with 1 272 nodes, 714 048 edges, and ω(G) = 53. Best-known solutions have size 53.
Available in DIMACS ascii format, or DIMACS binary format.
frb53-24-5
Graph with 1 272 nodes, 714 130 edges, and ω(G) = 53. Best-known solutions have size 53.
Available in DIMACS ascii format, or DIMACS binary format.
frb59-26-1
Graph with 1 534 nodes, 1 049 256 edges, and ω(G) = 59. Best-known solutions have size 59.
Available in DIMACS ascii format, or DIMACS binary format.
frb59-26-2
Graph with 1 534 nodes, 1 049 648 edges, and ω(G) = 59. Best-known solution has size 59.
Available in DIMACS ascii format, or DIMACS binary format.
frb59-26-3
Graph with 1 534 nodes, 1 049 729 edges, and ω(G) = 59. Best-known solutions have size 59.
Available in DIMACS ascii format, or DIMACS binary format.
frb59-26-4
Graph with 1 534 nodes, 1 048 800 edges, and ω(G) = 59. Best-known solutions have size 59.
Available in DIMACS ascii format, or DIMACS binary format.
frb59-26-5
Graph with 1 534 nodes, 1 049 829 edges, and ω(G) = 59. Best-known solutions have size 59.
Available in DIMACS ascii format, or DIMACS binary format.
frb100-40
Graph with 4 000 nodes, 7 425 226 edges, and ω(G) = 100. Best-known solution has size 98.
Available in DIMACS ascii format, or DIMACS binary format.
last update, 26 Oct 2015