KEYWORDS: challenge graphs, maximal independent set, maximal clique, clique-finding, transposition-correcting code, deletion-correcting code, code for Z-channel, code for asymmetric channel, Varshamov-Tenengolts codes, non-classical codes, non-standard codes, Lovasz theta numbers.
This is a collection of graphs arising from coding theory in which we would very much like to know the sizes of the maximal independent sets.
p edge 64 543
followed by 543 lines like
e 1 2
e 1 3
e 1 20
...
indicating that there are edges from node 1 to 2, from node 1 to 3,
from node 1 to 20, etc.
The nodes are labeled consecutively starting at 1. Each edge is specified just once.
The files have been gzipped. To uncompress them, run gunzip on them.
(See the DIMACS Implementation Challenges web page for further details about the format.)
1 14 20 21 35 48 55 58 66 79 86 89 100 101 120 123
and Magma has confirmed that no larger independent set exists.
1 15 22 25 36 37 60 61 67 88 91 103 106 113 127 130 144 151 154 166 169 190 196 197 220 221 232 235 242 256and David Applegate has confirmed that no larger independent set exists (see Ref. [Sl00]). (Confirmed by N. J. A. Sloane using Cliquer [NO03], July 04, 2003.)
1 16 23 26 38 41 63 68 69 94 108 109 115 131 156 157 168 171 178 199 202 209 224 239 246 249 258 280 283 295 298 305 320 326 329 351 366 372 373 388 389 414 428 429 435 456 459 466 481 496 503 506
(see Ref. [Sl00]).
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) show that 52 is best possible.
April 29, 2002: Ketan Narendra Patel , a post-doctoral researcher in the Electrical Engineering department at the University of Michigan working with Professor Igor Markov, confirms that 52 is best possible.
He says: "We formulated the problem as an integer linear program. Each vertex is represented by a binary variable, with a 1 signifying membership in the independent set. If two vertices share an edge we impose the constraint that the sum of their variables must be less than or equal to 1 (both cannot be members). We find the size of the largest independent set by maximizing the sum of all of the variables. We solved the problem using the optimization program CPLEX 7.00."
1 24 27 39 42 49 70 73 96 111 118 121 132 133 159 174 180 181 204 205 211 226 252 253 259 286 300 301 307 328 331 338 353 376 379 391 394 401 432 439 442 463 470 473 484 485 511 514 540 541 552 555 562 583 586 593 624 631 634 646 649 672 687 694 697 718 724 725 739 766 772 773 799 814 820 821 844 845 851 866 892 893 904 907 914 929 952 955 976 983 986 998 1001 1024
(see Ref. [Sl00]).
March 21, 2005: Brian Borchers (see below) has given an upper bound of 95, showing that the size of a maximal independent set is either 94 or 95.
June 30, 2005: Brian Borchers has shown that 94 is the answer. He says: "This was finally solved by a branch and bound calculation using the Lovasz theta number SDP bounds. The computation required 298 hours on 16 processors of an IBM p690 system at the National Center for Supercomputer Applications."
1 28 29 40 43 50 71 74 81 120 123 134 137 176 183 186 207 214 217 228 229 256 260 261 288 303 310 313 334 340 341 355 383 396 397 403 418 446 449 476 477 488 491 498 515 543 558 564 565 588 589 595 610 638 648 651 658 673 700 701 728 731 743 746 753 775 778 785 824 827 848 855 858 870 873 911 918 921 932 933 960 963 991 1006 1012 1013 1026 1054 1068 1069 1075 1096 1099 1106 1121 1148 1149 1159 1162 1169 1208 1211 1232 1239 1242 1254 1257 1286 1289 1328 1335 1338 1359 1366 1369 1380 1381 1408 1422 1428 1429 1443 1471 1474 1502 1516 1517 1523 1540 1541 1568 1583 1590 1593 1614 1620 1621 1635 1663 1676 1677 1683 1698 1726 1729 1756 1757 1768 1771 1778 1800 1803 1810 1825 1852 1853 1880 1883 1895 1898 1905 1936 1943 1946 1958 1961 1988 1989 2016 2031 2038 2041
(see Ref. [Sl00]), but it is possible that a larger independent set exists. March 21, 2005: Brian Borchers (see below) has given an upper bound of 174, so the answer here is in the range 172-174.
Confirmed by S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk [BPS03], November 28, 2001.
On Apr 28, 2001, Guenter Stertenbrink reported that this graph contains an independent set of size 16, which is therefore a lower bound on the maximal size.
Confirmed by S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk [BPS03], November 28, 2001; also by Johan Claes Nov 27, 2002.
One example is {1, 8, 43, 64, 121, 344, 402, 500, 564, 689, 830, 897, 904, 939, 1017, 1024}.
On Sep 20 2003 James B. Shearer reported that he has shown that the independence number of this graph is indeed 16. He says:
"I did this by exhaustive search helped by the following two observations:"1. We may assume the vertices corresponding to the all 0's vector and to the all 1's vector are included in a maximal independent set (since their neighborhoods are cliques).
"2. We may assume at least half the vertices in the independent set correspond to vectors with first coordinate 0 (since the graph is symmetric with respect to mapping vertices to their complements as 0-1 vectors).
"The search took about 750 seconds on a 43p-140 RS/6000 workstation (which uses a 332 Mhz 604e powerpc chip)."
1 8 57 64 197 334 482 508 628 643 792 875 1017 1078 1149 1193 1392 1604 1761 1793 1854 1869 1992 2047
Comments from Pablo San Segundo, Dec 04 2015: The search for a maximal clique in the graph 2dc.2048 has now finished. The answer is 24 (which was already known to be a lower bound).
The total time was 16.4 days using a 20-core XEON with 128Gb. 18-cores out of the 20 were in fact used.
The solution was found by a strong heuristic algorithm during pre-processing (about 5s). The actual search time was used “only” to prove optimality. The actual maximum clique algorithm is our most recent variant based on infra-chromatic BBMCX, described here, but as yet unpublished: https://www.researchgate.net/profile/Pablo_San_Segundo.
The project was carried out by Pablo San Segundo and Jorge Artieda, Polytechnic University of Madrid (UPM) and Center of Automation and Robotics (CAR). Supported by National Grant DPI 2014-53525-C3-1-R .
April 29, 2002: Ketan Narendra Patel confirmed that 110 is best possible. Confirmed also by N. J. A. Sloane using Cliquer [NO03], July 07, 2003.
On Apr 28, 2001, Guenter Stertenbrink reported that this graph contains an independent set of size 188.
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) increased the lower bound to 196.
July 17, 2003: N. J. A. Sloane used Cliquer [NO03] to show that the size of a maximal independent set is 196. This took 200 hours on a MAC OS X.
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) reported that this graph contains an independent set of size 352.
May 15, 2005: Brian Borchers (see below) has obtained an upper bound of 362, as follows:
Comp Bound Best known 1 1 1 opt 2 4 4 opt 3 13 13 opt 4 33 32 opt 5 59 55 opt 6 76 71 7 76 71 8 59 55 opt 9 33 32 opt 10 13 13 opt 11 4 4 opt 12 1 1 opt Best known: 352 Best bound: 362The smaller components are easily (within a few hours each) handled by either his Lovasz theta-based branch and bound code or by MINTO on the integer programming formulation, but the two largest components haven't cracked yet.
July 27, 2005: Brian Borchers reports that "Using my branch and bound code, I've lowered the bounds on components 6 and 7 of 1tc.2048 to 73. This puts an overall bound of 356 on the size of the MIS. Each of these computations took about 48 hours on my desktop machine. I've also gotten times for getting the bounds down to 74 and 75.
"Exponential extrapolation from the computations that I've done suggests that it would take about 100 CPU days to prove that 71 is optimal for each of these components. So, I'm working with a student at ASU to parallelize the branch and bound code and run it on a large cluster. This should bring the solution time down to a reasonable day or two."
Oct 16 2009: Brian Borchers reports that: "I've finally resolved problem 1tc.2048. 352 is optimal. I used my SDP based branch and bound code to resolve the p6 component (which is isomorphic to the p7 component.) It took about 2 weeks of time on my new machine (with two quad core Intel Xeon 5530 processors) and over 1,000,000 nodes in the B & B tree to solve the problem.
(An earlier version of this page said 48, but that was a simple arithmetic error - the 9 subgraphs contain maximal independent sets of sizes 1, 2, 6, 10, 12, 10, 6, 2, 1, respectively, and the sum of these numbers is 50, not 48! Thanks to several correspondents for pointing this out.)
Confirmed by N. J. A. Sloane using Cliquer [NO03], July 09, 2003.
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) reported that this graph contains an independent set of size 171.
April 14, 2005: Brian Borchers has confirmed that the correct answer is 171.
For example, nodes { 1, 2, 4, 8, 9, 11, 15, 16, 25, 26, 30, 34, 36, 45, 52, 56, 59, 63, 69, 71, 79, 96, 97, 98, 102, 113, 116, 117, 123, 124, 128, 129, 138, 140, 153, 156, 157, 175, 191, 195, 196, 200, 208, 211, 218, 225, 231, 233, 236, 240, 245, 247, 255, 258, 265, 269, 279, 306, 313, 317, 329, 333, 334, 370, 380, 381, 385, 394, 404, 419, 431, 441, 449, 454, 456, 457, 461, 464, 474, 483, 487, 494, 497, 501, 504, 509, 512, 516, 520, 528, 530, 538, 543, 548, 556, 560, 561, 570, 574, 576, 583, 610, 612, 616, 621, 625, 630, 640, 642, 655, 665, 668, 682, 733, 737, 740, 744, 762, 767, 772, 773, 776, 781, 784, 786, 790, 797, 799, 800, 801, 819, 820, 827, 828, 836, 837, 846, 863, 864, 869, 874, 884, 889, 892, 898, 903, 904, 912, 919, 921, 930, 942, 947, 957, 960, 961, 964, 968, 973, 976, 977, 986, 990, 994, 996, 1009, 1011, 1012, 1020, 1021, 1024}.
The sizes of the maximal independent sets in the components are as follows:
Component MIS 1 1 2 3 3 9 4 21 5 33 6 37 7 33 8 21 9 9 10 3 11 1 Total 171The maximal independent sets for each component were shown to be optimal by formulating an integer program and then solving it with the help of the "MINTO" [MINTO] integer programming code. This is essentially what Patel did for 1dc.512, but here it was done separately on each connected component.
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) report that this graph contains an independent set of size 316.
May 15, 2005: Brian Borchers (see below) has obtained an upper bound of 328, as follows:
Component Theta Bound Best Known 1 1 1 opt 2 3 3 opt 3 11 11 opt 4 31 28 opt 5 54 52 opt 6 69 63 7 69 63 8 54 52 opt 9 31 28 opt 10 11 11 opt 11 3 3 opt 12 1 1 opt Best known: 316 Best bound: 328The smaller components were all handled by integer programming (or by his SDP-based branch and bound code), but the two largest components have not cracked yet.
Nov 04 2009: Brian Borchers reports that: I was finally able to resolve the large components of 1et.2048. The MIS for the two large components of this graph is of size 63, so the MIS for the entire graph is of size 316. This was done using the integer linear programming formulation of the problem and Gurobi 2.0, a recently released branch and cut code for integer programming that turned out to be extremely efficient for this problem.
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) increased the lower bound to 379.
In March 2005 Brian Borchers computed the Lovasz theta numbers for many of these graphs. This gives an upper bound on the size of the largest independent set. The results are as follows.
(These results have been incorporated in the above paragraphs.)
Problem Theta Bound 1dc.64 10.0000 10 1dc.128 16.841880(**) 16 1dc.256 30.0000 30 1dc.512 53.0307 53 1dc.1024 95.9847 95 1dc.2048 174.7290 174 1et.64 18.8000 18 1et.128 29.2309 28* 1et.256 55.1142 53* 1et.512 104.4204 102* 1et.1024 184.2260 180* 1et.2048 342.0288 338* 1tc.64 20.0000 20 1tc.128 38.0000 38 1tc.256 63.3999 63 1tc.512 113.4002 112* 1tc.1024 206.3042 205* 1tc.2048 374.6431 372* 1zc.128 20.6667 20 1zc.256 38.0000 38 1zc.512 68.7500 68 1zc.1024 128.6667 128 1zc.2048 237.4000 237 1zc.4096 - 2dc.128 5.2424 5 2dc.256 7.4618 7 2dc.512 11.7678 11 2dc.1024 - 2dc.2048 -He remarks that, for the tc and et problems, it is possible to get tighter bounds by computing the theta numbers for each of the connected components, the resulting improvements are marked with asterisks (*).
(**) Entry corrected by Alexander Engau, Sep 10 2010