| Labelstyle: | font-weight:bold |
| Headerstyle: | background: #DD9 |
| Abovestyle: | background: #DD9 |
| Label1: | Developers: |
| Data1: | Insilab (National Institute of Chemistry Slovenia) |
| Label2: | Development status: |
| Data2: | Active |
| Label3: | Written in: |
| Data3: | C++ |
| Label4: | Type: |
| Data4: | graph theory, maximum clique algorithm, clique problem |
| Label5: | License: |
| Data5: | GNU General Public License |
| Label6: | Website: |
The MaxCliqueDyn algorithm is an algorithm for finding a maximum clique in an undirected graph.
MaxCliqueDyn is based on the MaxClique algorithm, which finds a maximum clique of bounded size. The bound is found using a coloring algorithm. MaxCliqueDyn extends MaxClique to include dynamically varying bounds.
This algorithm was designed by Janez Konc and its description was published in 2007.[1] In comparison to earlier algorithms, MaxCliqueDyn has an improved coloring algorithm (ColorSort) and applies tighter, more computationally expensive upper bounds on a fraction of the search space. Both improvements reduce time to find maximum clique. In addition to reducing time, the improved coloring algorithm also reduces the number of steps needed to find a maximum clique.
The MaxClique algorithm[2] is the basic algorithm from which MaxCliqueDyn is extended. The pseudocode of the algorithm is:
procedure MaxClique(R, C) is Q = Ø, Qmax = Ø while R ≠ Ø do choose a vertex p with a maximum color C(p) from set R R := R\ if |Q| + C(p)>|Qmax| then Q := Q ⋃ if R ⋂ Γ(p) ≠ Ø then obtain a vertex-coloring C' of G(R ⋂ Γ(p)) MaxClique(R ⋂ Γ(p), C') else if |Q|>|Qmax| then Qmax := Q Q := Q\ else return end while
where Q is a set of vertices of the currently growing clique, Qmax is a set of vertices of the largest clique currently found, R is a set of candidate vertices, and C its corresponding set of color classes. The MaxClique algorithm recursively searches for a maximum clique by adding and removing vertices to and from Q.
MaxClique uses an approximate coloring algorithm to obtain set of color classes C. In the approximate coloring algorithm, vertices are colored one by one in the same order as they appear in a set of candidate vertices R, so that if the next vertex p is non-adjacent to all vertices in the same color class, it is added to this class, and if p is adjacent to at least one vertex in every one of existing color classes, it is put into a new color class.
The MaxClique algorithm returns vertices R ordered by their colors. Vertices
v\inR
C(v)<{|Qmax|}-{|Q|}+1
The ColorSort algorithm improves on the approximate coloring algorithm by taking into consideration the above observation. Each vertex is assigned to a color class
Ck
k<{|Qmax|}-{|Q|}+1
k\geq{|Qmax|}-{|Q|}+1
Ck
Ck
k\geq{|Qmax|}-{|Q|}+1
Ck
k
C(v)=k
The pseudocode of the ColorSort algorithm is:
procedure ColorSort(R, C) is max_no := 1; kmin := |Qmax| − |Q| + 1; if kmin ≤ 0 then kmin := 1; j := 0; C1 := Ø; C2 := Ø; for i := 0 to |R| − 1 do p := R[i]; k := 1; while Ck ⋂ Γ(p) ≠ Ø do k := k+1; if k > max_no then max_no := k; Cmax_no+1 := Ø; end if Ck := Ck ⋃ ; if k < kmin then R[j] := R[i]; j := j+1; end if end for C[j−1] := 0; for k := kmin to max_no do for i := 1 to |Ck| do R[j] := Ck[i]; C[j] := k; j := j+1; end for end for
Example
The graph above can be described as a candidate set of vertices R = , and used as input for both the approximate coloring algorithm and the ColorSort algorithm. Either algorithm can be used to construct the following table:
| k | Ck | |
|---|---|---|
| 1 | 7(5), 5(2) | |
| 2 | 1(4), 6(3), 8(2) | |
| 3 | 4(4), 2(3), 3(3) |
The MaxCliqueDyn algorithm extends the MaxClique algorithm by using the ColorSort algorithm instead of approximate coloring algorithm for determining color classes. On each step of MaxClique, the MaxCliqueDyn algorithm also recalculates the degrees of vertices in R regarding the vertex the algorithm is currently on. These vertices are then sorted by decreasing order with respect to their degrees in the graph G(R). Then the ColorSort algorithm considers vertices in R sorted by their degrees in the induced graph G(R) rather than in G. By doing so, the number of steps required to find the maximum clique is reduced to the minimum. Even so, the overall running time of the MaxClique algorithm is not improved, because the computational expense
O(|R|2)
The pseudocode of the MaxCliqueDyn algorithm is:
procedure MaxCliqueDyn(R, C, level) is S[level] := S[level] + S[level−1] − Sold[level]; Sold[level] := S[level−1]; while R ≠ Ø do choose a vertex p with maximum C(p) (last vertex) from R; R := R\; if |Q| + C[index of p in R] > |Qmax| then Q := Q ⋃ ; if R ⋂ Γ(p) ≠ Ø then if S[level]/ALL STEPS < Tlimit then calculate the degrees of vertices in G(R ⋂ Γ(p)); sort vertices in R ⋂ Γ(p) in a descending order with respect to their degrees; end if ColorSort(R ⋂ Γ(p), C') S[level] := S[level] + 1; ALL STEPS := ALL STEPS + 1; MaxCliqueDyn(R ⋂ Γ(p), C', level + 1); else if |Q| > |Qmax| then Qmax := Q; Q := Q\; else return end while
Value Tlimit can be determined by experimenting on random graphs. In the original article it was determined that algorithm works best for Tlimit = 0.025.