Maximum Clique Search Algorithm

Prerequisites: Clique

Introduction

In computer science, the clique problem refers to the computational problem of finding cliques (subsets of vertices that are all adjacent to each other, also known as complete subgraphs) in a given graph.

The clique problem also manifests in real life. For example, consider a social network where vertices represent users and edges represent mutual acquaintance between two users. Then finding a clique corresponds to finding a group of people who all know each other.

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

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

Explanation

The idea is to use recursion and backtracking, maintaining a list of vertices. Each time a vertex is added, we check whether the current set of vertices still forms a clique. If adding the vertex would break the clique property, we backtrack to a state that satisfies the condition and try adding a different vertex.

The reason for using a backtracking strategy is that we do not know in advance whether a vertex \(v\) will ultimately be part of the maximum clique. If the recursive algorithm chooses \(v\) as a member of the maximum clique but fails to find a maximum clique, it should backtrack and search for a solution without \(v\).

Process

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

1. Initialize sets \(R\) and \(X\) as empty, and set \(P\) as the set of all vertices in the graph.
2. Each time, take a vertex \(v\) from set \(P\). When \(P\) is empty, there are two cases:
   1. Set \(R\) is a maximum clique, and set \(X\) is empty.
   2. No maximum clique is found, then backtrack.
3. For each vertex \(v\) taken from set \(P\), perform the following:
   1. Add vertex \(v\) to set \(R\), then recursively call the algorithm on sets \(R\), \(P\), and \(X\).
   2. Remove vertex \(v\) from set \(P\) and add it to set \(X\).
   3. If both sets \(P\) and \(X\) are empty, then set \(R\) is a maximum clique.

This method can be further optimized. To save time and allow the algorithm to backtrack faster, a pivot vertex can be selected for searching. Another optimization is to sort all vertices at the beginning and enumerate them in order of their indices to avoid duplication.

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

Implementation Code

#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] represents the size of the maximum clique that can be formed after the i-th point.
  // st[i][j] represents the set of points needed for the i-th level of DFS in the algorithm, storing points that could potentially be part of the maximum clique.

  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 point i in the set of the num-th level
      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 points after i in the num-th level that are connected to i, and add them to the (num+1)-th level 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 first level 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 Problems

POJ 2989: All Friends

Problem summary: Given \(n\) people and \(m\) pairs of friends, find the number of maximum cliques.

Idea: Template problem, requires using 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 no vertices are disallowed; accumulate answer  
     for each vertex v in Some: // Enumerate each element in Some  
         BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v))   
         // Add v to All; obviously only friends of v can be candidates; only friends of v in None will affect subsequent steps  
         Some := Some - {v} // Already searched, remove from Some and add to None  
         None := None ⋃ {v} 

To save time and allow the algorithm to backtrack faster, we can optimize by selecting a pivot vertex \(v\).

We know that the algorithm described above will inevitably repeat many calculations of previously computed maximal cliques before backtracking.

Taking the three sets \(R\), \(P\), and \(X\) mentioned earlier as an example:

Consider the following: take a vertex \(u\) from the set \(P\cup X\). To form a maximal clique with set \(R\), the vertices chosen must be from \(P\cap N(u)\) (where \(N(u)\) represents the neighbors of \(u\)).

If after choosing \(u\), we could also choose a neighbor \(v\) of \(u\) to join the maximal clique, then we only need to choose \(u\). This reduces redundant calculations for \(v\) later. We only need to consider vertices that are not adjacent to \(u\).

C++ implementation with optimization:

Implementation Code

#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 Undirected Graph
• POJ 1129 Radio Station

References

• Clique problem - Wikipedia
• Maximal Clique and Maximum Clique in Undirected Graphs (Bron–Kerbosch Algorithm)
• Maximum Clique Problem — Bron–Kerbosch Algorithm
• Maximum Clique Problem

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用