Find maximum clique with recursive function

26 views (last 30 days)
hmhuang
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.
  5 Comments

Sign in to comment.

Accepted Answer

Jan
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.
  7 Comments
breksam Amr
breksam Amr on 12 Sep 2021
@Mehrail Nabil did you find the answer i still don't understand it yet

Sign in to comment.

More Answers (0)

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!