Skip to content

CLUSTER Algorithm Design: Enumerating Maximal Cliques

Jump to bottom
ahakouz17 edited this page Feb 11, 2019 · 2 revisions

Enumerating Maximal Cliques

Introduction

Generally, three main types of clique related problems appear in literature:

  1. CLIQUE, the decision problem of whether a graph has a clique of size at least k.
  2. Max-Clique (MC), is the optimization version which searches for the maximum clique; i.e. the largest maximal clique in graph.
  3. All-Clique or Maximal Clique Enumeration (MCE), is the problem of enumerating all maximal cliques in a graph.

CLIQUE was one of the first known problems in NP-complete (Karp, 1972). While Max-Clique is in NP-Hard.

The best-known approximation algorithm for Max-Clique is 𝑂( \Large \frac{𝑛}}{(log2𝑛)<sup>2</sup>} ) (Boppana, 1990). It was proved that, unless NP = ZPP, for any ɛ > 0, Max-Clique cannot be efficiently approximated with a factor of n1-ɛ (Hastad, 1999).

In my project, I am considering the third and most complex problem of the three; All-Clique, which will be at least as hard as Max-Clique. All-Clique problem is NP-Hard because the maximum number of cliques in a graph G with n nodes is exponential in n. Moon and Moser (Moon, 1965) provided an upper bound f(n) on the maximum number of cliques which can be found in a graph with n nodes. f(n) = O(3n/3)

The algorithm I used for enumerating cliques is based on the Bron-Kerbosch algorithm BK (Bron, 1973) which is a recursive backtracking algorithm and it is considered as the most efficient exact algorithm known for generating all the cliques of a graph (Bomze, 1999).

  • Bomze, I. M. (1999). The maximum clique problem. In Handbook of combinatorial optimization (pp. 1-74). Boston, MA: Springer.
  • Boppana, R. (1990). Approximating Maximum Independent Sets by Excluding Subgraphs 1.
  • Bron, C. a. (1973). Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16(9), 575--577.
  • Hastad, J. (1999). Clique is hard to approximate within n^(1- e). Acta Mathematica, 182(1), 105--142.
  • Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85--103). Boston, MA: Springer.
  • Moon, J. W. (1965). On cliques in graphs. Israel journal of Mathematics, 3(1), 23--28.
Clone this wiki locally