Exact Solution of the Maximum Clique Problem

• Alexandre Prusch Züge UFPR
• Renato Carmo UFPR

Abstract

Several algorithms for the Maximum Clique Problem are available, many of them based on the branch and bound technique. In this work we describe a general branch and bound algorithm for the exact solution of the Maximum Clique Problem, we review eight algorithms from the literature and describe each one of them by modifying the general algoritm. We implemented these algorithms and ran several experiments. Experimental results are presented for comparison.

References

Bellare, M., Goldreich, O., e Sudan, M. (1995). Free bits, pcps and non-approximability-towards tight results. In Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on, p. 422–431. IEEE.

Bron, C. e Kerbosch, J. (1973). Algorithm 457: finding all cliques of an undirected graph. Commun. ACM, 16(9):575–577.

Carmo, R. e Züge, A. (2011). Branch and bound algorithms for the maximum clique problem under a unified framework. Journal of the Brazilian Computer Society, p. 1–15.

Carraghan, R. e Pardalos, P. M. (1990). An exact algorithm for the maximum clique problem. Operations Research Letters, 9(6).

Downey, R. e Fellows, M. (1999). Parameterized complexity, volume 5. Springer New York.

Duarte Jr., E. P., Garrett, T., Bona, L. C. E., Carmo, R., e Zuge, A. P. (2010). Finding stable cliques of planetlab nodes. In 2010 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN), p. 317–322. IEEE.

Fahle, T. (2002). Simple and fast: Improving a branch-and-bound algorithm for maximum clique. In Lecture Notes in Computer Science, p. 47–86. Springer Berlin / Heidelberg.

Garey, M. e Johnson, D. (1979). Computers and intractability. Freeman San Francisco.

Jian, T. (1986). An o(20.304n) algorithm for solving maximum independent set problem. IEEE Trans. Comput., 35(9):847–851.

Konc, J. e Janezic, D. (2007). An improved branch and bound algorithm for the maximum clique problem. MATCH Communications in Mathematical and in Computer Chemistry.

Moon, J. e Moser, L. (1965). On cliques in graphs. Israel Journal of Mathematics, 3(1):23–28.

Östergård, P. R. (2002). A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120(1-3):197–207.

Robson, J. (1986). Algorithms for maximum independent sets. Journal of Algorithms, 7(3):425–440.

Tarjan, R. E. e Trojanowski, A. E. (1976). Finding a maximum independent set. Technical report, Computer Science Department, School of Humanities and Sciences, Stanford University, Stanford, CA, USA.

Tomita, E. e Kameda, T. (2007). An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. Journal of Global Optimization, 37(1):95–111.

Tomita, E. e Seki, T. (2003). An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique. Springer Berlin/Heidelberg.

Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., e Wakatsuki, M. (2010). A simple and faster branch-and-bound algorithm for finding a maximum clique. In Rahman, M. e Fujita, S., editors, WALCOM: Algorithms and Computation, volume 5942, chapter 18, p. 191–203. Springer Berlin Heidelberg, Berlin, Heidelberg.

Tomita, E., Tanaka, A., e Takahashi, H. (2006). The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363(1):28–42.

Züge, A. (2011). Solução exata do problema da clique máxima. Master’s thesis, Universidade Federal do Paraná.