New Algorithms for Enumerating All Maximal Cliques
Kazuhisa Makino1 and Takeaki Uno2
1

Division of Mathematical Science for Social Systems, Graduate School of Engineering
Science, Osaka University, Toyonaka, Osaka, 560-8531, JAPAN.
makino@sys.es.osaka-u.ac.jp
2
National Institute or Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, JAPAN.
uno@nii.jp
Abstract. In this paper, we consider the problems of generating all maximal(bipartite) cliques in a given (bipartite) graph G = (V, E) with n vertices and medges. We propose two algorithms for enumerating all maximal cliques. One runs
with O(M (n)) time delay and in O(n2 ) space and the other runs with O(∆4 )time delay and in O(n + m) space, where ∆ denotes the maximum degree of G,
M (n) denotes the time needed to multiply two n × n matrices, and the latter one
requires O(nm) time as a preprocessing.
For a given bipartite graph G, we propose three algorithms for enumerating all
maximal bipartite cliques. The first algorithm runs with O(M (n)) time delay
and in O(n2 ) space, which immediately follows from the algorithm for the nonbipartite case. The second one runs with O(∆3 ) time delay and in O(n + m)
space, and the last one runs with O(∆2 ) time delay and in O(n + m + N ∆)space, where N denotes the number of all maximal bipartite cliques in G andboth algorithms require O(nm) time as a preprocessing.
Our algorithms improve upon all the existing algorithms, when G is either denseor sparse. Furthermore, computational experiments show that our algorithms forsparse graphs have significantly good performance for graphs which are generated randomly and appear in real-world problems.

1 Introduction
Enumerating all configurations that satisfy a given specification is a fundamental andwell-studied problem in combinatorics (see e.g., [13]). From both theoretical and practical points of view, it has taken on increasing importance in many scientific fields such as
artificial intelligence [10, 20], graph theory [14, 19, 21], operations research [16], data
mining [2, 3], web mining [15], bioinformatics, and computational linguistics. There
are several reasons to recognize enumeration as an important subject to study (see e.g.,[13]). Among them, we here mention the following two reasons.
One of the reasons is that there has been beginning to study the problems whose objective functions and/or constraints are difficult to be defined mathematically. For suchproblems, one of the simplest way is that we first generate all the candidates (polynomially many candidates or as many candidates as computational resources can allow), andthen choose one or a few from them according to a preference or plausibility relation
which may be based on subjective intuition. For example, in data mining, the procedure
above is usually used to find “interesting” objects, since it is difficult to define the term
“interesting.” Searching a webpage by keywords is another example. Search engines
usually output the pages including all or some keywords as the candidates of desired
webpages.

2

The second reason is the recent increase in computational power. 20 years ago, thecomputational power was too poor to enumerate all the candidates in practical time.
Even if it could be, it is hard to handle a great many candidates to be enumerated.
Recently, we can handle over 1 million data, and such data can be enumerated in practical time by an efficient algorithm. Hence, enumeration has been used to solve many
real-world problems in diverse areas.
This paper addresses the two problems of (1) generating all maximal cliques (equivalently, all maximal independent sets or all minimal vertex covers) of a given graph and(2) generating all maximal bipartite cliques of a given bipartite graph. Since cliques arefundamental graph objects, the problem of generating all maximal cliques is regarded
as one of the central problems in the field of enumeration, and has attracted considerable attention in the past (e.g., [7, 14, 16, 21]). The problems have not only theoreticalinterest, but also a number of potential applications in many areas (e.g., [15, 2, 3]). The
next section presents two examples for generating all maximal bipartite cliques.
In 1977, Tsukiyama et al. [21] first proposed an output-polynomial (or polynomial
total time) algorithm for generating all maximal cliques in a given graph G = (V, E)
that runs with O(nm) time delay (i.e., the computation time between any consecutive
output is bounded by O(nm), and the first (resp., last) output occurs also in O(nm) timeafter start (resp., before halt) of the algorithm) and in O(n+m) space. Here n = |V | andm = |E|. Lawler et al. [16] generalized this result (see [9] for further generalization).
Chiba and Nishizeki [7] reduced the time complexity to O(a(G)m), where a(G) isthe arboricity of G with m/(n − 1) ≤ a(G) ≤ m1/2 . Johnson et al. [14] proposedan algorithm which enumerates all maximal cliques in the lexicographical order. The
algorithm runs with O(nm) time delay, but it uses O(nN ) space, where N denotes thenumber of all maximal cliques of a given graph.
In this paper, we propose the following two algorithms for enumerating all maximal
cliques. The first one makes use of matrix multiplication, and runs with O(M (n)) timedelay and in O(n2 ) space, where M (n) is the time needed to multiply two n × nmatrices. Since it is known that matrix multiplication can be done in O(n 2.376 ) time [8],our algorithm improves upon the previous algorithms for dense graphs. For example, if
a given graph has m = Ω(n1.689 ) edges, our algorithm dominates all the existing ones.
The second algorithm runs with O(∆4 ) time delay and in O(n + m) space, where∆ is the maximum degree of G and it additionally requires O(nm) time as a preprocessing before generating the first maximal clique. This improves upon the previous
algorithms when a given graph G is sparse, e.g., n = Ω(∆2+ ) and m = Ω(n∆) forany  > 0. More generally, we consider graphs G having θ vertices with large degree(> ∆∗ ). We propose an algorithm that runs O((∆∗ )3 (∆∗ + θ) + θ3 ) time delay andin O((n + N ∗ )θ + m) space, where N ∗ denotes the number of all maximal cliques ofthe subgraph of G induced by vertices with large degree, and O(nm) time is required
as a preprocessing. This algorithm is motivated by practical applications such as web
networks, since the graphs obtained from those applications usually have a few vertices
with large degree. In this paper, we implement our second algorithm, and compare itwith the algorithms of Tsukiyama et al. by using graphs which are generated randomly
and appear in real-world problems. We show that our algorithm is much faster than thealgorithm of Tsukiyama et al.

3

Listing all maximal bipartite cliques is also well-studied (see e.g., [5, 11, 17, 18]).
Let us first note that the generation of all maximal bipartite cliques in a bipartite graph
G = (V1 ∪ V2 , E) can be seen as the one of all maximal cliques in the graph Ĝ obtained
from G by adding edges so that V1 and V2 both become cliques. This implies that thealgorithms above are applicable to generate all maximal bipartite cliques. Especially,
our algorithm that makes use of matrix multiplication improves upon all the existingalgorithms for dense graphs. However, if we consider practical applications, we need todevelop algorithms for sparse bipartite graphs. Note that Ĝ might be dense, even if G issparse. In this paper, we propose two algorithms for sparse bipartite graphs. The first one
runs in O(∆3 ) time delay and in O(n + m) space, and the second one runs with O(∆ 2 )time delay and in O(n + m + N ∆) space. Here both algorithms additionally requireO(nm) time as a preprocessing. Similar to non-bipartite clique case, these algorithms
improve upon previous algorithms for sparse graphs, and has good performance forcomputational experiments.
The rest of the paper is organized as follows. In Section 2, we present some examples of applications for our problems. Section 3 provides some preliminaries andintroduces notation. Section 4 explains the algorithms of Tsukiyama et al. and Johnson
et al. Section 5 presents an algorithm which uses matrix multiplication, and Sections 6
and 7 consider the problem for enumerating all maximal cliques and maximal bipartite
cliques for sparse graphs, respectively. Section 8 shows some results of computational
experiments.
Due to the space limitation, some proofs are omitted.

2 Applications of Maximal Clique Enumeration
In this section, we present two examples of the applications of generating all maximal
bipartite graphs. Some other applications can be found in the context of concept lattice[12] and in artificial intelligence, for example.
2.1 Web Communities
Consider a directed graph G = (V, A) (called web network) whose vertices and arcs
correspond to web pages and their links, respectively. Kumar et al. [15] regarded directed bipartite cliques (S1 , S2 ) (i.e., S1 × S2 ⊆ A) of G as communities of web
pages, i.e., the web pages in S2 may have similar topics and web pages in S1 may haveinterests in these topics, and considered generating directed bipartite cliques of G. They
first construct a graph G∗ with about 5,000,000 arcs by removing unnecessary vertices
and arcs from G, and then enumerate all directed bipartite cliques in the reduced graphG∗ . They show that directed bipartite cliques usually contain similar topics by checking
them by human hands. However, since G∗ contains a great number of bipartite cliques,
they could enumerate only those containing at most 10 vertices.
In this setting, it is natural to regard maximal directed bipartite cliques as good
representatives of communities. From a directed graph G = (V, A), let us construct
a bipartite (undirected) graph Ĝ = (V ∪ Ṽ , E) such that Ṽ (= {ṽ | v ∈ V }) isa copy of V and (v, ũ) ∈ E if and only if (v, u) ∈ A. Then there exists a one-toone correspondence between directed bipartite cliques in G and bipartite cliques in Ĝ.
Hence, our algorithms are applicable to generate all maximal directed bipartite cliques
in G∗

4

2.2 Closed Item Sets
Let I be a set of items and T be a family of sets in I (i.e., T ⊆ 2I ), where T ∈ T iscalled a transaction. For a given constant α, a subset S of I is called an (α-)frequent
set if at least α transactions of T include S. In data mining, we see that frequent setscharacterize database T , and investigate the enumeration of all frequent sets to findassociation rules from T , which is one of the main topics in data mining (e.g., [2,3]). However, since a database contains a great number of frequent sets if α is small,many researchers started studying the enumeration of all closed item sets, instead of all
frequent sets (e.g., [5, 17, 18, 25]). Here a frequent set S of I is called a closed item set,
if there is no other superset S 0 of S such that S 0 ⊆ T for any T ∈ T with S ⊆ T . Notethat the number of closed item sets is usually much smaller than the one of frequent sets
in database.
Pasquier et al. [17, 18] proposed algorithms based on back-tracking (and pruning unnecessary branches) to enumerate all closed item sets. Their experimental results show
that, if α is large, the number of closed item sets is quite small (up to about 100,000), andhence the algorithms are fast. However, since the algorithms are not output-polynomial,
they are not useful if we have a number of closed item sets, for example.
For a set of transactions T ⊆ 2I , we construct a bipartite graph GT = (V1 ∪ V2 , E)
by V1 = T , V2 = I and (u, v) ∈ E if and only if u ∈ V1 includes v ∈ V2 . Zaki and M.
Ogihara [25] showed that there exists a one-to-one correspondence between closed item
sets of T and maximal bipartite cliques in GT . Hence our algorithms can enumerate all
closed item sets in polynomial time delay. Since GT constructed from a database T is
usually sparse, it is shown [24] that our algorithms for sparse graphs work pretty well.

3 Definitions and Notations
This section introduces some notions and notations of graphs used in the subsequent
sections.
Let G = (V, E) be a graph with a vertex set V = {v1 , . . . , vn } and an edge set
E = {e1 , . . . , em }. If there is a partition V1 and V2 of V such that no two vertices
in Vi , i = 1, 2 are adjacent, then G is called bipartite and denoted by G = (V 1 ∪V2 , E). Throughout this paper, we assume without loss of generality that G is simple
and connected, since we deal with clique generation problems. We denote by A the
adjacency matrix of G, i.e., A is an n × n matrix such that its element a ij = 1 if
(i, j) ∈ E, and aij = 0, otherwise. For a vertex subset S ⊆ V , x(S) denotes thecharacteristic vector of S, i.e., the ith element of x(S) is 1 if vi ∈ S, and 0, otherwise.
For a vertex v of G, let Γ (v) = {u ∈ V | (u, v) ∈ E} and δ(v) = |Γ (v)|. We call
Γ (v) the neighbor of v, and δ(v) the degree of v. We denote by ∆ the maximum degreeof G. Similarly, for a vertex set S, let Γ (S) = {u ∈ V \ S | (u, v) ∈ E for some v ∈S}, and Γ (S) is called the neighbor of S. Let Λ(S) be the set of all v ∈ V \ S suchthat (v, u) ∈ E for any u ∈ S. By definition, we have Λ(S) ⊆ Γ (S) (⊆ V \ S). For avertex set S and an index i, let S≤i = S ∩ {v1 , . . . , vi }. For two vertex sets X and Y ,we say X is lexicographically larger than Y if the smallest vertex (i.e., a vertex withthe smallest index) in (X \ Y ) ∪ (Y \ X) is contained in X.
A vertex set K ⊆ V is called a clique if any two vertices in K are adjacent, and amaximal clique if no other clique contains K in addition. For a clique K, let C(K) denote the maximal clique that is the lexicographically largest among all maximal cliques

5containing K. It is clear that C(K) is not lexicographically smaller than K. For a bipartite graph G = (V1 ∪ V2 , E), a vertex set K is called a bipartite clique if any vertex
in K ∩ V1 is adjacent to any vertex in K ∩ V2 , and maximal if no other bipartite cliquecontains K in addition.

4 Basic Algorithms
In this section, we explain the algorithms of Tsukiyama et al. [21] and Johnson etal. [14]. We view their algorithms as the enumeration algorithms based on reverse search,where reverse search was introduced by Avis and Fukuda [4] to solve enumeration
problems efficiently. Note that our presentation of their algorithms is quite different
from theirs [21, 14], which may be of independent interest.
Let K0 denote the maximal clique that is the lexicographically largest among all
maximal cliques. For a maximal clique K (6= K0 ), we define a parent P (K) of K
by C(K≤i−1 ) such that i is the maximum index satisfying C(K≤i−1 ) 6= K. Such anindex i is called the parent index, denoted by i(K). Note that they are well-defined,
since K 6= C(K≤0 ) holds by K 6= K0 . Since P (K) is lexicographically larger thanK, this parent-child binary relation on maximal cliques is acyclic, and creates an in-tree
rooted by K0 .
Lemma 1. The parent-child relation constructs an in-tree rooted by K 0 .

tu

We call this in-tree the enumeration tree for maximal cliques of a graph G. Both algorithms [14, 21] traverse this enumeration tree. In order to traverse enumeration tree, wehave to compute a parent and children of a given maximal clique efficiently.
It is not difficult to see that a parent P (K) is computable from a maximal clique
K in linear time. However, it is not so trivial to compute from K its children. For amaximal clique K and an index i, we define
K[i] = C (K≤i ∩ Γ (vi )) ∪ {vi } .
(1)Lemma 2. Let K and K 0 be maximal cliques in G. Then K 0 is a child of K if and only
if K 0 = K[i] holds for some i such that(a) vi 6∈ K.
(b) i > i(K).
(c) K[i]≤i−1 = K≤i ∩ Γ (vi ).
(d) K≤i = C(K≤i ∩ Γ (vi ))≤i .
Moreover, if an index i satisfies (a) ∼ (d), then i is the parent index of K[i].
tu
Since C(K) can be computed from a clique K in O(m) time, by Lemma 2, we
can compute all children of a given maximal clique in O(nm) time. Therefore, we cantraverse the enumeration tree efficiently.
The algorithm of Tsukiyama et al. traverses the enumeration tree in a depth-firstmanner. Their algorithm starts with a root K0 , and find its children recursively. It is notdifficult to see that the algorithm requires O(nm) time delay and O(n + m) space.
The algorithm of Johnson et al. enumerates all maximal cliques in the lexicographically decreasing order. Their algorithm initializes a queue Q as Q = {K 0 }, iteratively extracts the lexicographically largest element K from Q and inserts into Q all

6

the children which are lexicographically smaller than K. The time complexity of theiralgorithm is same as the algorithm of Tsukiyama et al., however, it needs O(nN + m)
space, where N denotes the number of all maximal cliques.

5 Using Matrix Multiplication
In this section, we describe an algorithm that runs with O(M (n)) time delay and inO(n + m) space, where M (n) denotes the time needed to multiply two n × n matrices.
The algorithm uses matrix multiplication to find all children of a maximal clique when
we traverse the enumeration tree.
Let us start restating conditions (c) and (d) in Lemma 2.
Lemma 3. Let K be a maximal clique in G. Then an index i satisfies (c) if and only if
no index j satisfies the following three conditions.
(c-1) j < i.
(c-2) vj 6∈ K≤i ∩ Γ (vi ).
(c-3) vj is adjacent to all vertices in K≤i ∩ Γ (vi ) ∪ {vi }.

tuLemma 4. Let K be a maximal clique in G. Then an index i satisfies (d) if and only if
no index j satisfies the following four conditions.
(d-1) j < i.
(d-2) vj 6∈ K.
(d-3) vj is adjacent to all vertices in K≤j .
(d-4) vj is adjacent to all vertices in K≤i ∩ Γ (vi ).

tu

Let us now consider computing all indices i such that K[i] is a child of K. We
denote by Ia , Ib , Ic , and Id sets of the indices that satisfy conditions (a) ∼ (d) inLemma 2, respectively. It is clear that Ia can be constructed from K in O(n) time andO(n) space. Since i(K) can be computed in O(n + m) time, Ib can be constructed inO(n + m) time and O(n + m) space. From Lemma 3, we can compute I c as follows.
For ` = 1, 2, 3, let Q(c−`) be an n × n matrix whose (i, j) element is 1 if i and jsatisfy (c-`) in Lemma 3; otherwise, 0. Then it is clear that Q(c−1) and Q(c−2) can becomputed in O(n2 ) time and O(n2 ) space. However, we need O(n3 ) time to computeQ(c−3) if a naive method is applied. In order to compute Q(c−3) efficiently, let Q be thematrix whose ith row is x((K≤i ∩Γ (vi ))∪{vi }), where x(S) denotes the characteristic
vector of a set S ⊆ V . Then the (i, j) element of Q · A is the inner product of x((K ≤i ∩
Γ (vi )) ∪ {vi }) and x(Γ (vj )), where we recall that A denotes the adjacency matrix ofG, and hence it is |((K≤i ∩ Γ (vi )) ∪ {vi }) ∩ Γ (vj )|. We can see that the (i, j) element
is equal to |(K≤i ∩ Γ (vi )) ∪ {vi }| if and only if vj satisfies condition (c-3) in Lemma 3.
Thus Q(c−3) can be obtained in O(M (n)) time and O(n2 ) space by computing Q · A.
This implies that Ic can be constructed in O(M (n)) time and O(n2 ) space.
Similarly, Id can be constructed in O(M (n)) time and O(n2 ) space.
Therefore we have the following lemma.
Lemma 5. Let K be a maximal clique of a graph G, and let I denote the set of all
indices i such that K[i] is a child of K, i.e., I = Ia ∩ Ib ∩ Ic ∩ Id . Then I can becomputed in O(M (n)) time and O(n2 ) space.
tu7

We are now ready to describe our algorithm formally.
Algorithm A LLM AX C LIQUESInput: A graph G = (V, E).
Output: All maximal cliques of G.
Step 1. Compute the lexicographically largest maximal clique K0 of G.
Step 2. Call A LLC HILDREN(K0 ) and halt.

tuProcedure A LLC HILDREN(K) /* K is a maximal clique in G. */Step 1. Output K and compute the set I of all indices i such that K[i] is a child of K.
Step 2. For each i ∈ I do
Compute K[i] and call A LLC HILDREN(K[i]).
end.
Step 3. Return.

tu

Theorem 1. For a given graph G = (V, E), we can generate all maximal cliques of G
with O(M (n)) time delay and in O(n2 ) space.
tu

6 Algorithms for Sparse Graphs
In many practical applications, the given graphs G are sparse and only a few vertices
have large degree. Such examples can be found in web networks [1]. In such cases,Ω(n) time delay is not efficient enough. We first consider the simplest case in which allvertices have small degree, i.e., ∆ is small. We develop an algorithm for generating all
maximal cliques with O(∆4 ) time delay and in O(n + m) space, where O(nm) time isrequired as a preprocessing.
Since |K| ≤ ∆ + 1 holds for any clique K, given a clique K, we can compute
C(K) in O(∆2 ) and O(n + m) space by repeatedly augmenting K. Therefore, we cancompute K[i] and P (K) in O(∆2 ) time and O(n + m) space.
The following lemma shows that any maximal clique K (6= K0 ) has at most ∆2children.
Lemma 6. For a maximal clique K(6= K0 ), let K 0 be a child of K. Then vi(K 0 ) ∈Γ (K≤i(K 0 ) ) holds.
tuNote that K0 in general has Ω(n) children, and hence we compute them in O(nm)time as a preprocessing.
Let us now describe an algorithm that runs with O(∆4 ) time delay and in O(n + m)
space. The algorithm is similar to A LL M AX C LIQUES in Section 5, but different in thefollowing two points.
First, we do not construct I in Step 1 of Procedure A LL C HILDREN. If we store I in
the algorithm, we require O(n2 ) space in general, since we need O(n) space for each I
and the depth of the recursion is O(n). Instead, we check if K[i] is a child of K in thelexicographic order of i’s, and store the current i. This reduces the space to O(n).
Second, we do not always output a maximal clique K before recursively calling Procedure A LL C HILDREN. From Lemma 6, Step 1 of Procedure A LL C HILDREN checks
at most ∆2 indices i, if K 6= K0 . Since each check can be performed in O(∆2 ) time,
A LL C HILDREN requires O(∆4 ) time without considering its recursive calls. Thus, if
we do not modify the algorithm, it runs O(n∆4 ) time delay, since the depth of the8recursion is O(n). To reduce the time complexity, Procedure A LL C HILDREN outputs
K before all its recursive calls, if the depth of the current recursion is odd; output K
after all its recursive calls, otherwise. Although we skip the details, due to the space
limitation (see [23] for more details), this reduces the delay to O(∆4 ).
Theorem 2. For a given graph G = (V, E), all maximal cliques of G can be generated
with O(∆4 ) time delay and in O(n + m) space, where O(nm) time is required as apreprocessing.
tu
We next consider a more general case. Let G = (V = {v1 , . . . , vn }, E) be a graphsuch that δ(vi ) ≤ ∆∗ ( ∆) holds for i = 1, . . . , n − θ. Namely, only θ vertices
in G have large degree (> ∆∗ ). Let V ∗ = {vn−θ+1 , . . . , vn } and G[V ∗ ] denotes the
subgraph of G induced by V ∗ . We divide the family F of all maximal cliques into two
subfamilies F1 and F2 , where F1 has all maximal cliques that are contained in V ∗ andF2 = F \ F1 . Our algorithm first generates all maximal cliques in the graph G[V ∗ ]and keeps them in the memory. This can be done in O(θ 3 N ∗ ) time, by preparing theadjacency matrix of G[V ∗ ] as a preprocessing, where N ∗ denotes the number of all
maximal cliques in G[V ∗ ]. Note that this generates all maximal cliques in F1 , but may
generate some non-maximal cliques of G. Therefore, we remove them after generating
all maximal cliques in F2 . We remark that each non-maximal clique of G in F1 iscontained in a maximal clique in F2 , but no maximal clique in F2 contains more than
one maximal clique in F1 .
Formally our algorithm can be described as follows.
Algorithm A LLM AX C LIQUES ∗Input: A graph G = (V, E) such that the degree of vi (i = 1, . . . , n − θ) is at most ∆∗ .
Output: All maximal cliques of G.
Step 1. Generates all maximal cliques in the graph G[V ∗ ] and store them in Q.
Step 2. Compute the lexicographically largest maximal clique K0 of G.
Step 3. Call A LLC HILDREN(K0 ), output all sets in Q, and halt.
Procedure A LLC HILDREN ∗ (K) /* K is a maximal clique of G contained in F2 . */Step 1. if K contains a clique K 0 in Q then remove K 0 from Q.
/* K contains at most one clique in Q, which is not a maximal clique of G. */Step 2. Output K, compute I = {i | vi ∈ Γ (K≤i )}, and let I ∗ := ∅.
/* I is the set of candidates i such that K[i] is a child of K. */Step 3. For each i ∈ I do
if (K≤i ∩ Γ (vi )) ∪ {vi } 6⊆ V ∗then begin check conditions (a) ∼ (d) in Lemma 2.
if they are satisfied then I ∗ := I ∗ ∪ {i}.
end.
Step 4. For each i ∈ I ∗ doCompute K[i] and call A LLC HILDREN(K[i]).
/* Note that K[i] 6⊆ V ∗ by (K≤i ∩ Γ (vi )) ∪ {vi } 6⊆ V ∗ . */Step 5. Return.

t
u

t
u

Let us show the correctness of the algorithm via a series of lemmas.
Lemma 7. Let K ba a maximal clique that is contained in V ∗ . Then any descendantof K is contained in V ∗ .
tu9From this lemma, F2 (i.e., the set of all maximal cliques containing a vertex in
V \ V ∗ ) forms a connected component of the enumeration tree that contains K 0 . When
we generate all maximal cliques in F2 , we need not to traverse any descendant of a
maximal clique K contained in V ∗ . Therefore, Step 4 of Procedure A LL C HILDREN ∗checks if K[i] 6⊆ V ∗ before going to the recursion.
The next lemma, together with Lemma 6 shows that the number of candidates i suchthat K[i] is a child of K (6= K0 ) is small (see I in Step 2 of A LL C HILDREN ∗ ).
Lemma 8. Let K (6= K0 ) ba a maximal clique that contains a vertex in V \ V ∗ . Then
we have |{i | vi ∈ Γ (K≤i )}| ≤ (∆∗ + 1)(∆∗ + θ).
tu
Let us then consider constructing K[i] from K and i in Step 4 of A LL C HILDREN ∗ .
Lemma 9. Let K be a clique including a vertex v ∈ V \ V ∗ . Then C(K) can becomputed in O((∆∗ )2 ) time and O(nθ) space.
tu
From this lemma, if (K≤i ∩ Γ (vi )) ∪ {vi } 6⊆ V ∗ , then we only need O((∆∗ )2 ) time
to construct K[i] and to check conditions (a) ∼ (d) in Lemma 2. However, we note thatΩ(n) time is needed to construct K[i] if (K≤i ∩ Γ (vi )) ∪ {vi } ⊆ V ∗ . The following
lemma overcomes such difficulty.
Lemma 10. Let K be a maximal clique in G. If (K≤i ∩ Γ (vi )) ∪ {vi } ⊆ V ∗ , then K[i]is either not a child of K or a maximal clique contained in V ∗ .
tuBase on this lemma, Step 3 of A LL C HILDREN ∗ checks if (K≤i ∩ Γ (vi )) ∪ {vi } ⊆V before checking the conditions in Lemma 2.
We are now ready to present our theorem.
∗

Theorem 3. Let G be a a graph with n − θ vertices of degree at most ∆∗ . Then all
3
maximal cliques of G can be enumerated with amortized O((∆∗ ) (∆∗ + θ) + θ3 ) timedelay and in O((n + N ∗ )θ + m) space, where N ∗ denotes the number of all maximal
cliques in G[V ∗ ], and O(nm) time is required as a preprocessing.
tu
We remark that θ is small in practical cases. For example, we have θ ≤ log n in web
networks, where it is called power law [1, 15]. Therefore, the memory required in theapplication is not so large.

7 Enumeration of All Maximal Bipartite Cliques
In this section we consider enumerating maximal bipartite cliques in a bipartite graph.
For a bipartite graph G = (V1 ∪ V2 , E), let V1 = {v1 , . . . , vn1 } and V2 = {vn1 +1 ,. . . , vn }. We assume without loss of generality that no vertex v satisfies Γ (v) = V1 or
V2 . Recall that the generation of all maximal bipartite cliques in G can be regarded as
the one of all maximal cliques in the graph Ĝ obtained from G by adding edges so that
V1 and V2 both become cliques. We denote by Γ̂ and Ĉ as Γ and C for Ĝ; e.g., for a
vertex v, Γ̂ (v) = Γ (v) ∪ V1 if v ∈ V1 , and Γ̂ (v) = Γ (v) ∪ V2 if v ∈ V2 . We frequently
use Γ̂ and Ĉ instead of Γ and C to follow the results obtained in the previous sections.
For example, we define K[i] by
K[i] = Ĉ (K≤i ∩ Γ̂ (vi )) ∪ {vi }
(2)

10

Before describing our algorithms, let us present several good properties for bipartite
graphs to reduce the complexity of our problem.
Lemma 11. Let K (6= K0 ) be a maximal bipartite clique in G. If i > i(K), then we
have(i) K[i] can be represented as K[i] = K ∩ Γ (vi ) ∪ Λ(K ∩ Γ (vi )) .
(3)(ii) K[i]≤i−1 = K≤i ∩ Γ̂ (vi ) is equivalent to (c’) Λ(K ∩ Γ (vi )) − K = ∅.
(iii) K≤i = Ĉ(K≤i ∩ Γ̂ (vi ))≤i is always satisfied.

tuFrom Lemmas 2 and 11, we can reduce the delay to O(∆3 ) time for maximal bipartite cliques.
Theorem 4. Let G be a bipartite graph. Then all maximal bipartite cliques can begenerated with O(∆3 ) time delay and in O(n+m) space, where O(nm) time is required
as a preprocessing.
tuMoreover, the delay can be improved, if we use additional space.
Theorem 5. Let G be a bipartite graph. Then all maximal bipartite cliques can begenerated with O(∆2 ) time delay and in O(n + m + N ∆) space, where N denotes
the number of all maximal bipartite cliques in G and O(nm) time is required as apreprocessing.
tu

8 Computational Experiments
To evaluate the performance of our algorithms, we implement our algorithms for sparsegraphs in Theorems 2 and 4. We also implement the algorithm of Tsukiyama et al., andadapt it for bipartite graphs. Our codes are written in C, and the programs run in a PC
of Pentium III 500MHz with 256MB memory, whose OS is Linux. We examine thesealgorithm by using graphs that are generated randomly and taken from word data ofnewspapers in computational linguistics. Their experimental results can be found in thetable below.
Our random graphs are generated as follows. For given r and n, we constructa graph with n vertices such that vi and vj is adjacent with probability 1/2 if i +n − j (mod n) ≤ r or j + n − i (mod n) ≤ r. Bipartite graphs are constructedsimilarly, where we have |V1 | = |V2 |. We examine the cases of r = 10, 30 and
n = 1000, 2000, 4000, . . ., 256000. Exp. 1 and 2 (resp., Exp. 3) represent the results
for generating all maximal cliques. (resp., all maximal bipartite cliques). Exp. 1 (resp.
Exp. 3) shows the computational time to generate 10000 maximal cliques (resp., maximal bipartite cliques), as well as the number of all maximal cliques (resp., all maximal
bipartite cliques), where the computational time in the table is expressed in seconds,
and we only output the first 10000 cliques, if the computational time is over 3 hours.
Exp. 2 shows the the computational time of our algorithm per a maximal clique. We
also construct graphs G such that a few vertices of G have large degree, by adding 40

11vertices and edges adjacent to such vertices with probability 1/2 to graphs that are generated randomly for r = 10. Similarly to Exp. 2, Exp. 4 shows the the computationaltime of our algorithm per a maximal clique. Finally, we examine our algorithm for real
data P1, P2 and P3 which are taken from computational linguistics. The result is shownin Exp. 5.
Exp. 1: maximal cliques, r = 10, 30# vertices
Tsukiyama
Tsukiyama
Ours
Ours# output# output1000 2000 4000
8000 10000 16000 32000
64000 128000 256000
r = 10378
761 14103564
5123
r = 30 1755 4478 9912 21085 25345
r = 10
0.64
0.65
0.72
0.73
0.72
0.74
0.75
0.81
0.82
0.82
r = 30
4.41
4.44
4.47
4.56
4.51
4.54
4.55
4.91
4.88
4.88
r = 10 2774 5553 11058 22133 27624 44398 89120 179012 357657 716978
r = 30 20571 41394 83146 168049 209594 336870 675229 1352210 2711564 5411519

Exp. 2: maximal cliques , # vertices = 10000r
10
20
40 80 120 160 240 320 480 640
Ours 0.23 0.31 0.51 1 1.7 2.4 4.1 5.7 9.8 14
Exp. 3: maximal bipartite cliques, r = 10, 30# vertices
Tsukiyama
Tsukiyama
Ours
Ours# output# output1000 2000 4000 8000 10000 16000 32000 64000 128000 256000
r = 10 104
214
446
966
1260
r = 30 282
582 1190 2455
3100
r = 10 0.33
0.32
0.3
0.3
0.27
0.3
0.3
0.34
0.34
0.35
r = 30 1.08
1.08
1.09
1.1
1.09
1.11
1.12
1.22
1.22
1.26
r = 10 2085 4126 8316 16609 20862 33586 67143 134911 270770 541035
r = 30 9136 18488 40427 68597 101697 165561 322149 625385 1233989 8351277

Exp. 4: including 40 vertices with large degree, r = 10
# vertices 1000 2000 4000 8000 10000 16000 32000 64000 128000 256000
Ours 1.07
1.14
1.12
1.31
1.21
1.36
1.74
2.62
4.02
7.8
# output 9136 18488 40427 68597 101697 165561 322149 625385 1233989 2307135
Exp. 5: Real world data
P1
P2
P3

# vertices(V1 , V2 )22677,18484
33347,32757
20433,4297# edges # max cliques time
2470032700737 291
2334501892469 255
12771311860169 974

From the results in Exp. 1 and 3, we can see that our algorithms are much fasterthan the algorithm of Tsukiyama et al. The computational time of the algorithm ofTsukiyama et al. is linear to the number of vertices, but the one of our algorithm does
not depend the number of vertices, since the maximum degree is small. From Exp. 2,
we can see that the computational time of our algorithm per a maximal clique is closeto O(∆), which is almost linear in the output size. Exp. 4 shows that the computationaltime does not increase so much, even if the graphs contain some vertices of large degree.
Exp. 5 shows that problems P1, P2 and P3 can be solved efficiently. We note that thealgorithm of Tsukiyama et al. did not terminate for these problems by 3 hours.

References
1. A.-L. Barabasi, “LINKED – The New Science of Networks,” Perseus Publishing, 2002.
2. R. Agrawal and R. Srikant, Fast algorithms for mining association rules in large databases,
Proc. VLDB ’94, pp. 487–499, 1994.
3. R. Agrawal, H. Mannila, R. Srikant, H. Toivonen and A. I. Verkamo, Fast discovery of association rules, In Advances in Knowledge Discovery and Data Mining, MIT Press, pp. 307–328,
1996.

12
4. D. Avis and K. Fukuda, Reverse search for enumeration, Discrete App. Math., 65 (1996)
21–46.
5. E. Boros, V. Gurvich, L. Khachiyan and K. Makino, On the complexity of generating maximal frequent and minimal infrequent sets, Annals of Math. and Artif. Int., 39 (2003) 211-221.
6. E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan and K. Makino, Dual-bounded generatingproblems: All minimal integer solutions for a monotone system of linear inequalities, SIAM
J. Comput., 31 (2002) 1624–1643.
7. N. Chiba and T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput., 14(1985) 210-223.
8. D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progression, Journalof Symbolic Computation, 9 (1990) 251–280.
9. T. Eiter, G. Gottlob and K. Makino, New results on monotone dualization and generating
hypergraph transversals, SIAM J. Comput., 32 (2003) 514–537.
10. T. Eiter and K. Makino, On computing all abductive explanations, Proc. AAAI ’02, AAAI
Press, pp. 62–67, 2002.
11. D. Eppstein, Arboricity and bipartite subgraph listing algorithms, Info. Proc. Lett., 51 (1994)
207-211.
12. B. Ganter and R. Wille, Formal Concept Analysis, Springer, 1996.
13. L. A. Goldberg, Efficient algorithms for listing combinatorial structures, Cambridge University Press, New York, 1993.
14. D. S. Johnson, M. Yanakakis and C. H. Papadimitriou, On generating all maximal independent sets, Info. Proc. Lett., 27 (1998) 119–123.
15. S. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, Trawling the web for emerging
cyber-communities, Proc. the Eighth International World Wide Web Conference, Toronto,
Canada, 1999.
16. E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Generating all maximal independent
sets, NP-hardness and polynomial-time algorithms, SIAM J. Comput., 9 (1980) 558–565.
17. N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal, Discovering frequent closed itemsets for
association rules, Proc. the 7th ICDT Conference, LNCS 1540, Springer, pp. 398-416, 1999.
18. N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal, Closed set based discovery of small covers
for association rules, Proc. 15emes Journees Bases de Donnees Avancees, pp. 361-381,
1999.
19. R. C. Read and R. E. Tarjan, Bounds on backtrack algorithms for listing cycles, paths, andspanning trees, Networks, 5 (1975) 237-252.
20. B. Selman and H. J. Levesque, Support set selection for abductive and default reasoning,
Artif. Int., 82 (1996) 259–272.
21. S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirakawa, A new algorithm for generating all the
maximal independent sets, SIAM J. Comput., 6 (1977) 505–517.
22. T. Uno, Fast algorithms for computing web communities and frequent sets by using maximal
clique generations, In preparation.
23. T. Uno, Two general methods to reduce delay and change of enumeration algorithms, Technical Report of National Institute of Informatics, Japan, 2003.
24. T. Uno, T. Asai, H. Arimura and Y. Uchida, LCM: An efficient algorithm for enumerating frequent closed item sets, Workshop on Frequent Itemset Mining Implementations (FIMI’03).
25. M. J. Zaki and M. Ogihara, Theoretical foundations of association rules,” 3rd SIGMOD
Workshop on Research Issues in Data Mining and Knowledge Discovery, June 1998.