The Flat Graph Generator

Source Code

Source code in C is available here.

Description

This is the program used to generate the flat graph instances that are available through DIMACS and from Michael Trick's set of Graph Coloring Instances. A description of this class of graphs can be found in Exploring the k-colorable Landscape with Iterated Greedy co-authored with Feng Luo.

This generator will generate n-vertex k-partite graphs in which

  1. Each partition has either ceil(n/k) or floor(n/k) vertices
  2. The number of edges assigned is very close to the expected number of edges given the probability p and partitioning.
  3. The edges are selected at random from the the pairs in AxB subject to the constraints that
    1. for any a in A deg(a in AxB) <= ceil(e_{AB} / |B|) + flatness
    2. for any b in B deg(b in AxB) <= ceil(e_{AB} / |A|) + flatness

Thus, if flatness is 0, the graph is fairly uniform, while as flatness increases the variation in degree may also increase. However, the variation should always be less than that of an equi-partite graph.

The output is written to a file called 

         flat###_##_#.col
         where ### = number of vertices,
                ## = Number of partitions
                 # = flatness
Any pre-existing file of the same name is overwritten.

Here is an example run: 

Enter
        number of vertices 20
        density(10ths of percent) 500
        number of partitions 3
        flatness 0
        random seed 39112
This produced the output file flat20_3_0.col. The generator produces output in the DIMACS standard format. Descriptions of this and translators to binary formats can be found in Michael Trick's Graph Coloring Instances .

Discussion

This generator was written after a conversation with Craig Morgenstern at the DIMACS Challenge workshop. Given the results of the coloring of graphs with higher variability in the paper with Feng Luo, and the improvement in hiding cliques using the graphs described in Camouflaging Independent Sets in Quasi-Random Graphs co-authored with Mark Brockington, we thought similar reductions in variance might make the coloring problem more difficult.

This seems to be the case. Although using Iterated Greedy, and other algorithms seems to leave the ridge defined by edge density versus partition number in the same approximate location, the time (i.e. number of iterations) is increased dramatically over equi-partite graphs near the ridge. (See pages 47-50 in TR92-07 Iterated Greedy Graph Coloring and the Difficulty Landscape for a description of the ridge.)

It is suggested that experimenters test their algorithms by varying the edge density, partition number, number of vertices and flatness. This of course means a fairly large number of tests!

I would be interested in hearing of results on these. Also let me know about any useful modifications to the generator or any problems. E-mail to joe@cs.ualberta.ca.

Joe Culberson

April 1, 1995