There are two parts to this.

  1. Program an exponential-time (or worse) solution to two NP-complete problems.
     This is to be done by thinking about it, it isn't very difficult.
     Actually write the programs.

  2. Find out how each of those problems solves the other.
     I recommend you think about it first. Wouldn't it be nice if you found the solution?
     But finding the solution yourself isn't expected, it is just worth trying.
     Research (internet, books, but not other people) is the expected way.
     Explain the transformation process (in both directions) and why it is a valid solution
     sufficiently well to make it clear that you really understand it.


The first problem is a well-known one, about colouring maps.

A map of the world, or any large region of it, will show some number of countries, and
the countries are usually coloured to make it easy to see their boundaries. Naturally,
any two countries that share a border anywhere must have different colours.

Can a given map be rendered properly in three or fewer colours?

There is a nice quick algorithm that can colour any possible map successfully with
just four colours. It is not difficult to come up with a map that can not be coloured
with just three colours.

The question is not to do the colouring, but just to find out if it is possible, for
any given map, to colour it with only three colours. And remember you are not expected
to do it at all efficiently.

A very big hint is that for this problem, a simple graph can carry all the information
needed. Each country is a node in the graph, and there is an arc (connection) between
any two nodes whose countries have a shared border.


The second one is similar to a problem we looked at, but not the same. It is called
Clique Cover.

If a graph has N nodes and K is any number <= N, Can you find a way to divide the
nodes into K subgraphs such that each subgraph is a clique, and every one of the
N nodes is in exactly one of them. If you don't remember what a clique is, look in
your notes.


So to repeat, the assignment is to program a solution to both accepting that it will
be apallingly slow for all but trivial instances of the problems.

Then probably thorugh research, describe and justify the correctness of a method for
reducing a problem of each kind into a problem of the other kind.

Note, it is not necessary that the K in clique cover must be 3. Perhaps it could be,
perhaps not.