Author: Shalin Shah
A simple random search algorithm for the maximum clique problem in Java. A clique of a graph is a set of vertices in which each pair in the set have an edge between them i.e. it is a complete subgraph. A clique of maximum size is called the maximum clique. Finding the maximum clique of a graph is an NP-hard problem, and it it not possible to approximate the problem within a constant factor of the optimum. The code uses an adjacency list format for the graph; so it does not require a lot of memory, and is quite fast for moderately large graphs. It finds reasonably good solutions for most graphs in the DIMACS benchmarks.
This algorithm performs the following steps:
1) Create an initial clique using a greedy algorithm based on non-increasing degrees of the nodes
and call it gBest
2) Randomly remove two vertics from the clique created in step one.
3) Add vertices to the incomplete clique returned by step two in order of non-increasing degrees.
4) If the complete clique formed in step 3 is better than gBest, gBest = (3).
5) Continue from step 2 till some termination criteria (Number of Iterations)
Instances are available here and here (DIMACS). Please remove all comments and other extraneous text from the graph text instance file.
Cite this code
@misc{shah2016randomized,
title={Randomized heuristic for the maximum clique problem},
author={Shah, Shalin},
year={2016},
DOI={10.5281/zenodo.3818578}
}
Usage:
- Compile the code using any Java compiler (Tested using Java 8) - e.g. javac *.java - Then run java MaxClique filename iterations - e.g. java MaxClique instances/C2000.5.CLQ 100000 - Typical number of iterations is 100000 - To use the code as an API, please see the main method in MaxClique.java
Results:
Results on some randomly chosen DIMACS graphs. Please see this page for these and other maximum clique benchmarks (some with known optimum solutions). (You may have to run the algorithm a couple of times to get the best solution. It is quite fast and takes only a few seconds for 100,000 iterations).
| Instance | Nodes (Vertices) | Edges | Best Known Clique | This Algorithm |
| p_hat1500-3 | 1500 | 847244 | 94 | 93 |
| C2000.5 | 2000 | 999836 | 16 | 15 |
| p_hat700-1 | 700 | 60999 | 11 | 9 |
| C500.9 | 500 | 112332 | 57 | 53 |
| brock800_4 | 800 | 207643 | 26 | 19 |
| gen400_p0.9_75 | 400 | 71920 | 75 | 50 |
Cited By:
- Choi, Jang-Ho, et al. "Distributed coordination of IoT-based services by using a graph coloring algorithm." Computer Software and Applications Conference (COMPSAC), 2013 IEEE 37th Annual. IEEE, 2013.
- Muklason, Ahmad. "Hyper-heuristics and fairness in examination timetabling problems." Philosophy (2017)