#
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

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