The Challenge

For the third mini-project, each of the groups will compete against each other to solve a combinatorial problem on a data set.

Any approach you can think of is allowed (even brute force, if your computer is strong enough :), although the teacher would certainly enjoy it if the groups at least tried some of the methods discussed in the course.

On the last Project Day, the groups will show their results and describe their approaches to the rest of the class.

The problem is to find the maximum clique of a graph (MAX-CLIQUE). A clique is a set of vertices such that every vertex in the set is connected to every other vertex in the set. This problem is in the set NP-Complete.

The data set is the anonymized pleonast.com social graph. In the pleonast social graph, friend connections are one-way but for purposes of this problem any friend connection is considered to connect both members.

Your task is to find the largest subset of users such that every user in the set is connected to every other user in the set.

Two data formats are provided, one in mysqldump format suitable for immediately populating a mysql database, and one in CSV (comma separated value) format.

• Datafile in SQL format
• Datafile in CSV format

You should implement in your code a fitness function that evaluates a candidate solution for how fit they are. You should track the number of times this function is called, not forgetting to cache already-evaluated solutions if possible.

It will be interesting to see not only which group can find the largest clique, but also which group finds it using the fewest number of fitness function calls.

The group that finds the largest clique by the Project Day using the smallest number of fitness function calls will win a prize