Draft:MaxCliqueDyn algorithm

MaxCliqueDyn algorithm

insilab.org/maxclique/
Class	maximum clique algorithm

The MaxCliqueDyn algorithm is an algorithm for finding a maximum clique in an undirected graph. It is based on a basic algorithm (MaxClique) which finds a maximum clique of bounded size. The bound is found using improved coloring algorithm. The MaxCliqueDyn is the basic algorithm extended to include dynamically varying bounds. This algorithm was designed by Janez Konc and description was published in 2007. In comparison to earlier algorithms described in the published article the MaxCliqueDyn algorithm is improved by an improved approximate coloring algorithm (ColorSort) and by applying 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 improved coloring algorithm also reduces the number of steps needed to find a maximum clique.

MaxClique algorithm

The MaxClique algorithm is the basic algorithm of MaxCliqueDyn algorithm. The pseudo code of the algorithm is:

   Procedure MaxClique(R, C)
       Q = Ø; Qmax = Ø;
       while R ≠ Ø do
           choose a vertex p with a maximum color C(p) from set R;
           R := R\{p};
           if |Q| + C(p)>|Qmax| then
               Q := Q ⋃ {p};
               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\{p};
           else return
       end while

where Q is a set of vertices of the currently growing clique, Q_max 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 maximum clique by adding and removing vertices to and from Q.

Coloring algorithm (ColorSort)

In the MaxClique algorithem the approximate coloring algorithm is used to obtain set of color classes C. The ColorSort algorithm is an improved algorithm of the approximate coloring algorithm. 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 some 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. By looking at the MaxClique algorithm it is clear that vertices v∈R with colors C(v) < |Q_max|−|Q|+1 will never be added to to the current clique Q. Therefore sorting those vertices by color is of no use to MaxClique algorithm.

ColorSort algorithm

   Procedure ColorSort(R, C)
       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]; {the i-th vertex in R}
           k := 1;
           while Ck ⋂ Γ(p) ≠ Ø do
               k := k+1;
           if k > max_no then
               max_no := k;
               Cmax_no+1 := Ø;
           end if
           Ck := Ck ⋃ {p};
           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

MaxCliqueDyn algorithm

MaxCliqueDyn algorithm

   Procedure MaxCliqueDyn(R, C, level)
       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\{p};
           if |Q| + C[index of p in R] > |Qmax| then
               Q := Q ⋃ {p};
               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\{p};
           else return
       end while

External links

• www.example.com