Clique Hiding Generator

Source Code

Source code in C is available here.

Description

This is the program DELTA used to generate the graphs described in Camouflaging Independent Sets in Quasi-Random Graphs by Mark Brockington and Joseph Culberson.

Instructions for compiling are included in the documentation. Here is a sample run:

tees% GraphGen -g20 -c3 -p0.500 -d0 -s889113
Input file name to write file to: (".b" will be appended)
sample
c Graph Generator
c
c By: Mark Brockington (brock@cs.ualberta.ca)
c and Joe Culberson (joe@cs.ualberta.ca)
c
c Graph Size:20, Clique Size: 3
c Seed:889113, Edge Density: 0.50000
c Depth 0 Hiding
c
c Clique Elements are:
c 19 17 15
c
c Estimated Size of Uncompressed File: 0.0MB
c
p edge 20 92

The file is written in DIMACS compressed format. See Michael Trick's set of Graph Coloring Instances. for a description of this format and for various translation programs.

NOTE: The graph hides a clique in its present form. To convert to an independent set hider, change the code after the line

  /* Now, invert the graph to change the ind. set to a clique */


KNOWN BUGS:

The hidden solution in the output is "off by one";  that is, the hidden solution values are indexed from 0 to n-1, rather than the DIMACS format of 1..n.  I think it is too late to change this without causing a descrepancy problem with older versions, and with the DIMACS files.

Joe Culberson

April 1, 1995 Last Update March 31, 2004.