Study On Exact Algorithm For Maximum Clique Problem

Many real-world problems such as signal transmission, investment scheme selection, coding error diagnosis and so on can be converted to the maximum clique problem?MCP, Maximum Clique Problem?, and it also can be applied into the fields of pattern recognition and computer vision. The MCP is a very classic NP- complete problem in the field of combinatorial optimization problem, and it has a high practical significance and theoretical value.The object of MCP is to find a complete subgraph with maximum size in a undirected graph, and the algorithm for this problem can be divided into two categories: exact algorithms and heuristic algorithms. Heuristic algorithm is a non-deterministic algorithm and an approximate solution can be found by a litter time, but the solution is not guaranteed as the optimal one. However, exact algorithms does not have this defect, in theory, exact algorithm can kill any MCP in unlimited time theoretic. The paper is focused on the exact algorithm of the maximum clique problem.In this paper, details of the current major precise algorithms were analyzed, such as C&P, MCQ, MaxCliqueDyn and so on. The results pointed out the direction of potential improvement of exact algorithm being three: first, to change the selection order of the vertices when branch; second, to improve the algorithm to compute the initial lower bound; third and to improve the algorithm to get more precise upper bound after branch. In this paper, experiment and analysis are conducted and a new exact algorithm for MCP named MMC is proposed.Test result of DIMACS benchmarks show that MMC works very well than other algorithms in some graph like gen400_p0.9₅5, gen400_p0.9₆5 and gen400_p0.9₇5. Meanwhile the average efficiency of MMC algorithm is also better than most of other exact algorithm for MCP. Therefore, MMC is considered to be an efficient and promising algorithm.