Sample Settings for the Graph Generator
These settings are designed to sample across the "phase transition" for
several of the graph classes. See the manual for more explanation of the classes
and what they are designed to test. If you find these too difficult (or easy)
then try different values for the number of vertices. The samples at fixed
k=3 should (mostly) be solveable in "reasonable" time using a conversion
to SAT and solvers such as satz-rand. The evacuation graphs with larger
k are notable in that non-optimal solutions tend to be farther from
the solution in terms of number of colors used than is the case for flat
and iid graphs using iterated greedy. Alternatively, we can view this as
shifting the boundary of the phase transition. I am curious to see how other
solvers do on these.
To see what the input values set run the generator program interactively.
Parameters such as "seed", "k" and "p" should have suitable numerical
values substituted as indicated. All inputs below specify no cheat in the
output. All output graphs are DIMACS ASCII format. You should do a number
of graphs at each setting.
NOTE: The generator guarantees the graph is k-colorable, but
does not guarantee the chromatic number. In particular, on the sparser side
of the "transition", that is for higher k when p is fixed,
or lower values of p for fixed k, the chromatic number is
typically less than the hidden coloring.
Equipartite IID graphs
- P=1/2 varying number of colors. Generator input:
0 seed 2 500 k 1 0.5 0
Vary k from k=25 to k= 70.
- Colors fixed at 3, varying edge density. Generator input:
0 seed 2 500 3 1 p 0
Vary p from p=0.010 to p=0.020 in steps of 0.001.
Refine by varying p in steps of 0.00025 near the middle of the range. If
these are too easy increase n from 500.
Flat Graphs (flatness 0)
- P=0.5, colors varying Generator input:
0 seed 6 n k 0.5 0 0
For n=300 vary k from k=16 to k=30 in steps of 2.
For n=1000 vary k from k=40 to k=90 in steps of 5.
- Colors fixed at 3, varying edge density. Generator input:
0 seed 6 500 3 p 0 0
Vary p from p=0.010 to p=0.020 in steps of 0.001.
Refine by varying p in steps of 0.00025 near the middle of the range. If
these are too hard, use n=300.
Evacuation Graphs
- P=0.5, colors varying Generator input:
0 13765 2 500 k 7 0.5 0 f 1 k 0
Fix f=0.0, vary k (two places!) from k=15 to k=70.
For harder instances, vary f slightly. For example, f=0.001 is enough to
generally guarantee that even at k=50 only the hidden coloring will be correct
(n=500).
- For colors fixed to 3-colors, varying p.
0 13765 2 700 3 7 p 0 f 1 3 0
Set f to 0.0. Vary p from p=0.009 to p=0.020 in steps of 0.001. Varying
f may produce harder instances. n=700 may be too hard at the transition,
try n=650