4-Clique Problem The clique problem is to find cliques in a graph. A clique is a set of vertices that are all adjacent - connected - to each other. A 4-clique is a set of 4 vertices that are all connected to each other. So in this example of the 4-Clique Problem, we have a 7-vertex graph. A brute-force algorithm has searched every possible combination of 4 vertices and found a set that forms a clique: https://en.wikipedia.org/wiki/Clique_problem

4-Clique Problem

The clique problem is to find cliques in a graph.

A clique is a set of vertices that are all adjacent - connected - to each other.

A 4-clique is a set of 4 vertices that are all connected to each other.

So in this example of the 4-Clique Problem, we have a 7-vertex graph. A brute-force algorithm has searched every possible combination of 4 vertices and found a set that forms a clique:

https://en.wikipedia.org/wiki/Clique_problem

You should read the Wikipedia page for the Clique Problem (and then read wider if need be) if you need to understand more about it.

Note that the Clique Problem is NP-Complete and therefore when the graph size is large a deterministic search is impractical. That makes it an ideal candidate for an evolutionary search.

For this assignment you must suppose that you have been tasked to implement the 4-clique problem as an evolutionary algorithm for any graph with any number of vertices (an n-vertex graph). The algorithm succeeds if it finds a 4-clique.

To achieve this task you would need to:

• develop an understanding of the problem and the nature of the search space
• figure out how to represent solutions and calculate fitness
• figure out ways to perform techniques such as mutation, crossover and termination

...and so the questions below are designed to take you through some of those processes.

You are expected to fill in any gaps in your knowledge of combinatorial mathematics through independent study.

1. Provide an algebraic expression, in terms of n, for the size of the phenotypic search space (the number of possible combinations of 4 vertices), for an n-vertex graph. You may assume that n ≥ 4.

2. Explain how a valid genotype can be represented as a partial permutation of integers, providing an example for the case n=7.

3. If we choose to represent each genotype as a partial permutation, then provide an algebraic expression, in terms of n, for the size of the genetic search space (the number of possible valid genotypes), in terms of n. You may again assume that n ≥ 4.

4. By comparing the answers to questions 1 and 3 above, briefly comment on how this reflects the mapping of genotypes to phenotypes.

5. Suppose a candidate solution p, where p is a phenotype consisting of 4 vertices. Suppose that minimum fitness occurs when no pair of vertices in p are connected, and maximum fitness occurs when all pairs of vertices in p are connected. Explain using pseudocode how to calculate the fitness F of p.

6. Suppose we decided to use swap mutation. Explain why that would be either a good or bad idea.

7. Give two reasons why a termination criterion that only halts when a valid solution is found is insufficient.

8. Suggest an additional termination criterion to fix the problem in question 7 above.