Network Resources for the Maximum Clique Finding Problem

Last Update: 21.10.2008

Introduction

Unweighted case

Let G=(V,E) be an undirected graph, where V is the set of vertices and E is the set of edges. A clique is a complete subgraph of G, i.e. one whose vertices are pairwise adjacent. The maximum clique problem is a problem of finding maximum complete subgraph of G, i.e. a set of vertices from G that are pairwise adjacent. An independent set is a set of vertices that are pairwise nonadjacent. A graph coloring problem is defined to be an assignment of color to its vertices so that no pair of adjacent vertices shares identical colors. All those problems are computationally equivalent, in other words, each one of them can be transformed to any other.

It is well known that maximum clique finding is NP-complete problem.
Weighted case

The maximum-weight clique problem asks for clique of the maximum weight. The weighted clique number is the total weight of weighted maximum clique. It can be seen as a generalization of the maximum clique problem by assigning positive, integer weights to the vertices. Actually it can be generalized more by assigning real-number weights, but it is reasonable to restrict to integer values since it doesn’t decrease complexity of the problem. This problem is well known to be NP-hard.

Algorithms

This page currently represents algorithms that were presented in my dissertation. So, if you are interested in more details about algorithms' logic, how those are intended to work and references on other works then you can browse this study for more information.
The following papers are the most novel result of this research and contain latest algorithms' descriptions and definitions

D. Kumlander, An extended comparison of the best known algorithms for finding the unweighted maximum clique, In: Communications in Computer and Information Science, vol. 14: Modelling, Computation and Optimization in Information Systems and Management Sciences: Second International Conference MCO 2008, Metz, France - Luxembourg, Spetember 2008. Hoai An Le Thi , PAscal Bouvry, Tao Pham Dinh (eds), Springer-Verlag, 2008, p. 175 - 181 [pdf]
D. Kumlander, On importance of a special sorting in the maximum-weight clique algorithm based on colour classes, In: Communications in Computer and Information Science, vol. 14: Modelling, Computation and Optimization in Information Systems and Management Sciences: Second International Conference MCO 2008, Metz, France - Luxembourg, Spetember 2008. Hoai An Le Thi , PAscal Bouvry, Tao Pham Dinh (eds), Springer-Verlag, 2008, p. 165 - 174 [pdf]

Algorithms' Program Codes

This section primary was organized to provide a detail description of algorithms for programmers. It was very difficult to decide which language to use here, but finally we decided to go with Visual Basic 6.0. It is not an obvious choice for many people, but the reason is very simple - this language is so elementary that nearly any developer can understand that even if he never used that before. So you can understand and re-implement in another programming language.

Unweighted case
- Algorithm that is based on a heuristic vertex coloring
  Program listing available as: txt, html, cls (VB6 format)
- Algorithm that is based on a heuristic vertex coloring and backtracking by colour classes
  Program listing available as: txt, html, cls (VB6 format)
- Patric Östergård's algorithm: A fast algorithm for the maximum clique problem, Discrete Applied Mathematics, Vol. 120. (2002) 197-20
  More details can be found on the Cliquer homepage
  Program listing available as: txt, html, cls (VB6 format)
- R. Carraghan and P. M. Pardalos algorithm: An exact algorithm for the maximum clique problem. Op. Research Letters 9. (1990) 375-382
  Program listing available as: txt, html, cls (VB6 format)
- Source code of a program that was used to test algorithms on random graphs is also available as a zip file (rename zp to zip)
  PS: Can be run only if Visual Basic 6 is installed
Weighted case
- Algorithm that is based on a heuristic vertex coloring and a backtrack search
  Program listing available as: txt, html, cls (VB6 format)
- Patric Östergård's algorithm: A new algorithm for the maximum-weight clique problem. Nordic Journal of Computing, Vol. 8. (2001) 424-436
  More details can be found on the Cliquer homepage
  Program listing available as: txt, html, cls (VB6 format)
- Carraghan and Pardalos algorithm:
  A fast algorithm for the maximum clique problem, Discrete Applied Mathematics, Vol. 120. (2002) 197-20
  Unweighted algorithm applied to the weighted case
  A parallel algorithm for the maximum weight clique problem. Technical report CS-90-40, Dept of Computer Science, Pennsylvania State University (1990)
  Program listing available as: txt, html, cls (VB6 format)
- Source code of a program that was used to test algorithms on random graphs is also available as a zip file (rename zp to zip)
  PS: Can be run only if Visual Basic 6 is installed

License

Usefull links

Some graphs: Challenge Problems: Independent Sets in Graphs (Sloane)