# Find maximum clique with recursive function

28 views (last 30 days)
hmhuang on 9 Aug 2021
Commented: breksam Amr on 12 Sep 2021
I am solving an problem which has been stated and discussed here: maximum clique problem solve
As the OP showed in the above thread, the original version is inefficient because it is checking a bunch of sets of nodes that cannot possibly be part of a clique. So we need a smarter way to pick which nodes to check.
Therefore, based the tiny improvement in the accepted answer in maximum clique problem solve, I also tried:
1. disregard nodes with length < length(clique)
2. disregard nodes with the first element > clique(1)
3. disregard nodes with the last element < clique(end)
4. disregard nodes that are not in the follow list of first elemnt in the current clique
So my version of modification based on what @Jan wrote is changing line 15 to:
if ~any(node == clique) && length(graph{node}) >= length(clique) && graph{node}(1) <= clique(1) && graph{node}(end) >= clique(end) && any(node == graph{clique(1)})
Unfortunately, this runs for ~60 seconds on my computer, which is still not fast enough to pass the grader...
I also come up with the order of operands of && operator. So I change the above line to:
if any(node == graph{clique(1)}) && length(graph{node}) >= length(clique) && graph{node}(1) <= clique(1) && graph{node}(end) >= clique(end) && ~any(node == clique)
Although this gets a bit faster and runs for ~40 seconds on my computer, unfortunately this is still not fast enough to pass the grader...
I HOPE SOMEONE COULD PROVIDE SOME ADVICES.
ANY SUGGESTIONS WILL BE APPRECIATED.
Jan on 12 Aug 2021
Okay, it's clear now.

Jan on 12 Aug 2021
Edited: Jan on 12 Aug 2021
I've reduced the run time from 60 to 2 seconds using this method:
• Convert the {1 x N} cell array of vectors to a [N x N] logical array X, which is true, if an ID in a specific column follows an ID in a specific row.
• Omit elements of X if the corresponding elements of X.' are not true: A following cannot belong to a clique, if it points it is not mutual.
• Run a loop over the rows (or columns - X is symmetric now). Select the sumbatrix:
v = X(k, :);
Y = X(v, v);
• Convert this back to the original represantation using a cell vector and indices.
• Call the original function as suggested in the other thread
An alternative description of the idea: I do not search the complete graph, but for the k'th ID only the elements of graph(graph{k}) are considered. The others cannot be part of a clique, which contains the k'th node of the graph.
I do not post the code, because this is a question of a course. A clean solution would stay at the representation as logical array to apply the recursive search. But my lazy method yields an acceleration of factor 30 already by a divide and conquer approach without touching the actual algorithm.
breksam Amr on 12 Sep 2021
@Mehrail Nabil did you find the answer i still don't understand it yet