BHOSLIB: Benchmarks with Hidden Optimum Solutions for Graph Problems (Independent Set, Vertex Cover, Clique and Vertex Coloring)

------ Hiding Exact Solutions in Random Graphs


If you have any comments or need more instances for the following benchmarks, please send me an email.

Maximum Independent Set (MIS) and Minimum Vertex Cover (MVC)

The MIS and MVC benchmarks provided on this page are directly transformed from forced satisfiable SAT benchmarks of Model RB, with the set of vertices and the set of edges respectively corresponding to the set of variables and the set of binary clauses in SAT instances (Thanks to Klaus D. Witzel for bringing our attention to this transformation). In fact, based on Model RB and this transformation, we can get a new random graph model as follows:

  1. Generate n disjoint cliques, each of which has nα vertices (where α>0 is a constant);
  2. Randomly select two different cliques and then generate without repetitions pn2&#945; random edges between these two cliques (where 0<p<1 is a constant);
  3. Run Step 2 (with repetitions) for another rnlnn-1 times (where r>0 is a constant).

It is easy to see that for the graph model above, the size of maximum independent sets is at most n. Interestingly, determining if such a upper bound can be reached is equivalent to determining the satisfiability of the corresponding CSP and SAT instances of Model RB, and there is a one-to-one mapping between the solutions of these two problems. To hide an independent set of size n in the instances of this graph model, we first select a vertex at random from each disjoint clique to form an independent set of size n, and then in the above process of generating random edges, no edge is allowed to violate this maximum independent set. From the results of the paper "Many Hard Examples in Exact Phase Transitions with Application to Generating Hard Satisfiable Instances", it is expected that this method can be used to generate hard instances for graph algorithms (by use of the hardness of phase transitions, i.e. choosing appropriate values of &#945;, p and r), and thus can have potential applications in cryptography.

Note: All the benchmarks provided on this page are expressed in the DIMACS graph format.

Maximum Clique and Vertex Coloring

The following benchmarks are the complements of the graph instances above.

Remark: As mentioned before, finding optimum solutions to the above graph instances is equivalent to finding solutions to the corresponding forced satisfiable CSP and SAT instances of Model RB. It is worth noting that some corresponding SAT benchmarks of the above instances were used for SAT Competition 2004 (55 solvers). The results are summarized as follows (Note: Instances differing only in the suffix are equivalent, e.g. frb40-19-1.clq and frb40-19-1.cnf):

Forced Satisfiable CSP and SAT Benchmarks of Model RB

Pseudo-Boolean Benchmarks with Hidden Optimum Solutions
 

Back to Ke Xu's homepage.

Date Created: April 20, 2004. Last Updated: June 8, 2004.