Maximum Clique Search Algorithm

Prerequisite knowledge: Cliques

Introduction

In computer science, the clique problem is the computational problem of finding a clique in a given graph (a subset of vertices, all mutually adjacent, also called a complete subgraph).

The clique problem also appears in real life. For example, consider a social network in which graph vertices represent users and graph edges represent pairs of connected users who know each other. Then finding a clique means finding a group of people who all know one another.

If we want to find the largest group of mutually acquainted people in this social network, we need a maximum clique search algorithm.

We have already introduced the concept of a maximal clique; a maximum clique is a maximal clique with the greatest number of vertices.

Explanation

The idea is to use recursion and backtracking, storing vertices in a list and checking each time a vertex is added whether these vertices still form a clique. If adding a vertex means that the set can no longer be a clique, backtrack to a position satisfying the condition and add another vertex.

The reason for using backtracking is that we do not know whether a vertex $v$ is ultimately a member of a maximum clique. If the recursive algorithm chooses $v$ as a member of the maximum clique but does not find a maximum clique, it should backtrack and search for a solution to the maximum clique that does not contain $v$.

Process

The Bron–Kerbosch algorithm optimizes this idea. Its basic form recursively searches using three given sets: $R$, $P$, and $X$. The steps are as follows:

1. Initialize the sets $R,X$ as empty, and let $P$ be the set of all vertices in the graph.
2. Each time, take a vertex $v$ from set $P$. When the set contains no vertices, there are two cases:
   1. Set $R$ is a maximum clique; at this point, set $X$ is empty.
   2. There is no maximum clique; backtrack.
3. For each vertex $v$ taken from set $P$, process it as follows:
   1. Add vertex $v$ to set $R$, then recursively process sets $R,P,X$.
   2. Delete vertex $v$ from set $P$ and add vertex $v$ to set $X$.
   3. If both $P,X$ are empty, set $R$ is a maximum clique.

This method can be optimized further. To save time and make the algorithm backtrack faster, a pivot vertex can be selected for the search. Another optimization is to sort all vertices at the beginning and enumerate them in index order to prevent duplicates.

Implementation

Pseudocode

R := {}
P := node set of G 
X := {}

BronKerbosch1(R, P, X):
    if P and X are both empty:
        report R as a maximal clique
    for each vertex v in P:
        BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

C++ Implementation

#include <cstring>
#include <iostream>
using namespace std;
constexpr int MAXN = 105;

struct MaxClique {
  bool g[MAXN][MAXN];
  int n, dp[MAXN], st[MAXN][MAXN], ans;

  // dp[i] is the size of the maximum clique that can be formed after vertex i,
  // st[i][j] is the set of vertices needed by the dfs at level i of the algorithm; it stores vertices that may belong to one of the maximum cliques

  void init(int n) {
    this->n = n;
    memset(g, false, sizeof(g));
  }

  void addedge(int u, int v, int w) { g[u][v] = w; }

  bool dfs(int sz, int num) {
    if (sz == 0) {
      if (num > ans) {
        ans = num;
        return true;
      }
      return false;
    }
    for (int i = 0; i < sz; i++) {  // enumerate a vertex i in the set at level num
      if (sz - i + num <= ans) return false;  // pruning 1
      int u = st[num][i];
      if (dp[u] + num <= ans) return false;  // pruning 2
      int cnt = 0;
      for (
          int j = i + 1; j < sz;
          j++) {  // traverse vertices after i at level num that are adjacent to i, and add them to the level num+1 set
        if (g[u][st[num][j]]) st[num + 1][cnt++] = st[num][j];
      }
      if (dfs(cnt, num + 1)) return true;
    }
    return false;
  }

  int solver() {
    ans = 0;
    memset(dp, 0, sizeof(dp));
    for (int i = n; i >= 1; i--) {
      int cnt = 0;
      for (int j = i + 1; j <= n; j++) {  // initialize the level 1 set
        if (g[i][j]) st[1][cnt++] = j;
      }
      dfs(cnt, 1);
      dp[i] = ans;
    }
    return ans;
  }

} maxclique;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  while (cin >> n, n) {
    maxclique.init(n);
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        int x;
        cin >> x;
        maxclique.addedge(i, j, x);
      }
    }
    cout << maxclique.solver() << '\n';
  }
  return 0;
}

Example

Approach: This is a template problem; use the Bron–Kerbosch algorithm.

Pseudocode:

 BronKerbosch(All, Some, None):  
     if Some and None are both empty:  
         report All as a maximal clique // all vertices have been selected, and there are no vertices that cannot be selected; increment the answer  
     for each vertex v in Some: // enumerate every element in Some  
         BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v))   
         // Add v to All. Clearly, only people who are friends with v can be candidates; in None, only those who are friends with v can affect what follows.
         Some := Some - {v} // already searched; remove it from Some and add it to None  
         None := None ⋃ {v} 

To save time and make the algorithm backtrack faster, we can optimize it by selecting a pivot vertex $v$.

We know that the algorithm above inevitably repeats the process of calculating maximal cliques that have already been calculated, and then backtracks.

Taking the three sets $R$, $P$, and $X$ mentioned above as an example:

Consider the following problem: take a vertex $u$ from $P\cup X$. To form a maximal clique with set $R$, the selected vertex must be a vertex in $P\cap N(u)$ ($N(u)$ denotes the vertices adjacent to $u$).

If, after selecting $u$, we select a vertex $v$ adjacent to $u$ and it can also be added to the maximal clique, then selecting only $u$ is sufficient. This can reduce duplicate calculations of $v$ later. We only need to select vertices that are not adjacent to $u$ afterward.

The optimized C++ implementation is as follows:

#include <cstring>
#include <iostream>
using namespace std;
constexpr int MAXN = 130;
bool mp[MAXN][MAXN];
int some[MAXN][MAXN], none[MAXN][MAXN], all[MAXN][MAXN];
int n, m, ans;

void dfs(int d, int an, int sn, int nn) {
  if (!sn && !nn) ++ans;
  int u = some[d][0];
  for (int i = 0; i < sn; ++i) {
    int v = some[d][i];
    if (mp[u][v]) continue;
    for (int j = 0; j < an; ++j) all[d + 1][j] = all[d][j];
    all[d + 1][an] = v;
    int tsn = 0, tnn = 0;
    for (int j = 0; j < sn; ++j)
      if (mp[v][some[d][j]]) some[d + 1][tsn++] = some[d][j];
    for (int j = 0; j < nn; ++j)
      if (mp[v][none[d][j]]) none[d + 1][tnn++] = none[d][j];
    dfs(d + 1, an + 1, tsn, tnn);
    some[d][i] = 0, none[d][nn++] = v;
    if (ans > 1000) return;
  }
}

int work() {
  ans = 0;
  for (int i = 0; i < n; ++i) some[1][i] = i + 1;
  dfs(1, 0, n, 0);
  return ans;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  while (cin >> n >> m) {
    memset(mp, 0, sizeof mp);
    for (int i = 1; i <= m; ++i) {
      int u, v;
      cin >> u >> v;
      mp[u][v] = mp[v][u] = true;
    }
    int tmp = work();
    if (tmp > 1000)
      cout << "Too many maximal sets of friends.\n";
    else
      cout << tmp << '\n';
  }
  return 0;
}

Exercises

• ZOJ 1492 Maximum Clique
• POJ 1419 Maximum Clique in an Undirected Graph
• POJ 1129 Radio Transmission

References

• Clique problem - Wikipedia
• Maximal and maximum cliques in an undirected graph (Bron–Kerbosch algorithm)
• Maximum clique problem—Bron–Kerbosch algorithm
• Maximum clique problem