Exists m n k
------------
This software is covered by the CRAPL licence (see CRAPL-LICENSE.txt)
What Exists?
------------
Does there exist a simple graph with m vertices (i.e. order m) and n edges (i.e. size n) that
contains no cycles of length k-1 or less (i.e. has girth k)?
Required Software
-----------------
The program uses choco-2.1.0-basic.jar and a copy of it is in this directory or available
from the choco web site http://www.emn.fr/z-info/choco-solver/ You will need to get the
CLASSPATH to point to this (no help given here).
Compiling
---------
Do the following on the command line
>javac *.java
Running
-------
The program Exists takes as arguments
- m, the number of vertices in the graph (order)
- n, the number of edges in the graph (size)
- k, the minimum girth of the graph
- [witness] optional argument
It is run as follows (for example)
> java Exists 10 25 4
true
25[+0] millis.
34[+0] nodes
This says "Yes! There is a graph with 10 vertices and 25 edges of girth 4 and it took
me 25 milliseconds to discover this and I had to make 34 decisions."
You might run it as follows
>java Exists 10 25 4 witness
0 0000011111
1 0000011111
2 0000011111
3 0000011111
4 0000011111
5 1111100000
6 1111100000
7 1111100000
8 1111100000
9 1111100000
24[+0] millis.
34[+0] nodes
This then delivers a witness as a 0/1 adjacency matrix for a graph with those properties.
But what happens when there is no such graph?
>java Exists 10 26 4
false
249[+0] millis.
446[+0] nodes
It delivers false (and if you ask for a witness "no witness"). If we have already run with n=10, m=25 and k=4
and got "yes!" then we know that this is "extremal".
NOTE:
-----
This program is not optimized in any way whatsoever. It does not take into consideration
any features of the problem. It is slow. See the CRAPL license.
Patrick Prosser
19/04/2013