Clique and Colouring
--------------------

1. Modify cliqueDecision.mzn by adding variables and constraints
   such that it answers the clique decision problem ...
   "Given a graph G, is there a clique of size k?"

2. Run your program as follows

     mzn-gecode cliqueDecision.mzn data/g20.dzn -D"k = nn" -s

   where nn is the size of the clique to be found.

   NOTE: there is a java program that you can run to compare against

     java CliqueDecision data/g20.dzn nn

3. Investigate the following. Clique decision is one of the first NP-complete problems.
   Is the problem actually easy or is it hard? If some instances are hard, what makes
   them hard?

4. Find the largest clique, for each of the graphs in the data directory, using
   cliqueDecsion ... i.e. find the clique number

5. Modify maxClique.mzn such that it finds a maximum clique in a graph

6. Test maxClique.mzn to make sure it agrees with cliqueDecision. Also, what are
   runtimes like?

7. Modify gCol.mzn, adding appropriate variables and constraints, such that it answers the
   graph colouring problem "Can the graph G be coloured using at most k colours."

8. As in 4 above, find the smallest number of colours required to colour each of our
   graphs ... i.e. find the chromatic number. Also, as in 3 above, graph colouring is
   NP-complete, but is it actually hard? Investigate this.

9. Do you observe any relationship between the clique number and the chromatic number?

10. Have a break.


Patrick