Adapting the Bron-Kerbosch Algorithm for
Enumerating Maximal Cliques in Temporal Graphs∗

arXiv:1605.03871v2 [] 2 May 2017

Anne-Sophie Himmel1 , Hendrik Molter1 , Rolf Niedermeier1 , and
Manuel Sorge2
1

Institut für Softwaretechnik und Theoretische Informatik, TU Berlin,
Germany, anne-sophie.himmel@campus.tu-berlin.de,
{h.molter, rolf.niedermeier}@tu-berlin.de
2
Ben Gurion University of the Negev, Department of Industrial
Engineering and Management, Be’er Sheva, Israel,
sorge@post.bgu.ac.il
May 3, 2017

Abstract
Dynamics of interactions play an increasingly important role in
the analysis of complex networks. A modeling framework to capture
this are temporal graphs which consist of a set of vertices (entities in
the network) and a set of time-stamped binary interactions between
the vertices. We focus on enumerating ∆-cliques, an extension of the
concept of cliques to temporal graphs: for a given time period ∆, a
∆-clique in a temporal graph is a set of vertices and a time interval such that all vertices interact with each other at least after every ∆ time steps within the time interval. Viard, Latapy, and Magnien [ASONAM 2015, TCS 2016] proposed a greedy algorithm for enumerating all maximal ∆-cliques in temporal graphs. In contrast to this
approach, we adapt the Bron-Kerbosch algorithm—an efficient, recursive backtracking algorithm which enumerates all maximal cliques in
static graphs—to the temporal setting. We obtain encouraging results
both in theory (concerning worst-case running time analysis based on
the parameter “∆-slice degeneracy” of the underlying graph) as well
as in practice1 with experiments on real-world data. The latter culminates in an improvement for most interesting ∆-values concerning
running time in comparison with the algorithm of Viard, Latapy, and
Magnien.
∗
A preliminary version of this article appeared in the Proceedings of the 2016
IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining [10]. Parts of this work are based on the first author’s Bachelor thesis at TU Berlin [9].
1
Code freely available at http://fpt.akt.tu-berlin.de/temporalcliques/ (GNU
General Public License).

1

1

Introduction

Network analysis is one of the main pillars of data science. Focusing on
networks that are modeled by undirected graphs, a fundamental primitive
is the identification of complete subgraphs, that is, cliques. This is particularly true in the context of detecting communities in social networks.
Finding a maximum-cardinality clique in a graph is a classical NP-hard
problem, so super-polynomial worst-case running time seems unavoidable.
Moreover, often one wants to solve the more general task of not only finding one maximum-cardinality clique but to list all maximal cliques. Their
number can be exponential in the graph size. The famous Bron-Kerbosch
algorithm (“Algorithm 457” in Communications of the ACM 1973, [3]) addresses this task and still today forms the basis for the best (practical) algorithms to enumerate all maximal cliques in static graphs [4]. However, to
realistically model many real-world phenomena in social and other network
structures, one has to take into account the dynamics of the modeled system
of interactions between entities, leading to so-called temporal networks. In
a nutshell, compared to the standard static networks, the interactions in
temporal networks (edges) appear sporadically over time (while the vertex
set remains static). Indeed, as Nicosia et al. [22] pointed out, in many realworld systems the interactions among entities are rarely persistent over time
and the non-temporal interpretation is an “oversimplifying approximation”.
In this work, we use the standard model of temporal graphs. A temporal
graph consists of a vertex set and a set of edges, each with an integer timestamp. The generalization of a clique to the temporal setting that we study
is called ∆-clique and was introduced by Viard et al. [28, 29]. Intuitively,
being in a ∆-clique means to be regularly in contact with all other entities
in this ∆-clique. In slightly more formal terms, each pair of vertices in the
∆-clique has to be in contact in at least every ∆ time steps. A fully formal
definition is given in Section 2. We present an adaption of the framework of
Bron and Kerbosch to temporal graphs. To this end, we overcome several
conceptual hurdles and propose a temporal version of the Bron-Kerbosch
algorithm as a new standard for efficient enumeration of maximal ∆-cliques
in temporal graphs.

1.1

Related Work

Our work relates to two main lines of research. First, enumerating ∆-cliques
in temporal graphs generalizes the enumeration of maximal cliques in static
graphs, this being subject of many different algorithmic approaches (sometimes also exploiting specific properties such as the “degree of isolation”
of the cliques searched for) [3, 4, 12, 14, 16, 25]. Indeed, clique finding is
a special case of dense subgraph detection. Second, more recently, mining
dynamic or temporal networks for periodic interactions [17] or preserving

2

structures [26] (in particular, this may include cliques as a very fundamental pattern) has gained increased attention. Our work is directly motivated
by the study of Viard et al. [28, 29] who introduced the concept of ∆-cliques
and provided a corresponding enumeration algorithm for ∆-cliques. In fact,
following one of their concluding remarks on future research possibilities,
we adapt the Bron-Kerbosch algorithm to the temporal setting, thereby
outperforming their greedy-based approach in most cases.

1.2

Results and Organization

Our main contribution is to adapt the Bron-Kerbosch recursive backtracking algorithm for clique enumeration in static graphs to temporal graphs.
In this way, we achieve a significant speedup for most interesting time period values ∆ (typically two orders of magnitude of speedup) when compared to a previous algorithm due to Viard et al. [28, 29] which is based
on a greedy approach. We also provide a theoretical running time analysis
of our Bron-Kerbosch adaption employing the framework of parameterized
complexity analysis. The analysis is based on the parameter “∆-slice degeneracy” which we introduce, an adaption of the degeneracy parameter that
is frequently used in static graphs as a measure for sparsity. This extends
results concerning the static Bron-Kerbosch algorithm [4]. A particular feature to achieve high efficiency of the standard Bron-Kerbosch algorithm is
the use of pivoting, a procedure to reduce the number of recursive calls of
the Bron-Kerbosch algorithm. We show how to define this and make it work
in the temporal setting, where it becomes a significantly more delicate issue
than in the static case. In summary, we propose our temporal version of the
Bron-Kerbosch approach as a current standard for enumerating maximal
cliques in temporal graphs.
The paper is organized as follows. In Section 2, we introduce all main
definitions and notations. In addition, we give a description of the original
Bron-Kerbosch algorithm as well as two extensions: pivoting and degeneracy
ordering. In Section 3, we propose an adaption of the Bron-Kerbosch algorithm to enumerate all maximal ∆-cliques in a temporal graph, prove the
correctness of the algorithm and give a running time upper bound. Furthermore, we adapt the idea of pivoting to the temporal setting. In Section 4
we adapt the concept of degeneracy to the temporal setting and give an
improved running time bound for enumerating all maximal ∆-cliques. In
Section 5, we present the main results of the experiments on real-world data
sets. We measure the ∆-slice degeneracy of real-world temporal graphs, we
study the efficiency of our algorithm, and compare its running time to the
algorithm of Viard et al. [28], showing a significant performance increase due
to our Bron-Kerbosch approach. We conclude in Section 6, also presenting
directions for future research.

3

2

Preliminaries

In this section we introduce the most important notations and definitions
used throughout this article.

2.1

Graph-Theoretic Concepts

In the following we provide definitions of adaptations to the temporal setting
for central graph-theoretic concepts.
2.1.1

Temporal Graphs

The motivation behind temporal graphs, which are also referred to as temporal networks [11], time-varying graphs [22], or link streams [28], is to
capture changes in a graph that occur over time. In this work, we use the
well-established model where each edge is given a time stamp [2, 11, 28]. Assuming discrete time steps, this is equivalent to a sequence of static graphs
over a fixed set of vertices [5, 19]. Formally, the model is defined as follows.
Definition 1 (Temporal Graph). A temporal graph G = (V, E, T ) is defined

as a triple consisting of a set of vertices V , a set of time-edges E ⊆ V2 ×T ,
and a time interval T = [α, ω], where α, ω ∈ N, T ⊆ N and ω − α is the
lifetime of the temporal graph G.

The notation V2 describes the set of all possible undirected edges {v1 , v2 }
with v1 6= v2 and v1 , v2 ∈ V . A time-edge e = ({v1 , v2 }, t) ∈ E can be interpreted as an interaction between v1 and v2 at time t. Note that we will
restrict our attention to discretized time, implying that changes only occur at discrete points in time. This seems close to a natural abstraction of
real-world dynamic systems and “gives the problems a purely combinatorial
flavor” [20].
2.1.2

∆-Cliques

A straightforward adaptation of a clique to the temporal setting is to additionally assign a lifetime I = [a, b] to it, that is, the largest time interval such
that the clique exists in each time step in said interval. However, this model
is often too restrictive for real-world data. For example, if the subject matter
of examination is e-mail traffic and the data set includes e-mails with time
stamps including seconds, we are not interested in people who sent e-mails
to each other every second over a certain time interval, but we would like to
know which groups of people were in contact with each other, say, at least
every seven days over months. One possible approach would be to generalize the time stamps, taking into account only the week an e-mail was sent,
resulting in a loss of accuracy in the data set. The constraint of each pair of
vertices being connected in each time step can be relaxed by introducing an
4

additional parameter ∆, quantifying how many time steps may be skipped
between two connections of any vertex pair. These so-called ∆-cliques were
introduced by Viard et al. [28, 29] and are formally defined as follows.
Definition 2 (∆-Clique). Let ∆ ∈ N. A ∆-clique in a temporal graph G =
(V, E, T ) is a tuple C = (X, I = [a, b]) with X ⊆ V , b − a ≥ ∆, and I ⊆ T
such that for all τ ∈ [a, b − ∆] and for all v, w ∈ X with v 6= w there exists
a ({v, w}, t) ∈ E with t ∈ [τ, τ + ∆].
In other words, for a ∆-clique C = (X, I) all pairs of vertices in X interact with each other at least after every ∆ time steps during the time interval I. We implicitly exclude ∆-cliques with time intervals smaller than ∆.
It is evident that the parameter ∆ is a measurement of the intensity of
interactions in ∆-cliques. Small ∆-values imply that the interaction between
vertices in a ∆-clique has to be more frequent than in the case of large ∆values. The choice of ∆ depends on the data set and the purpose of the
analysis.
We can also consider ∆-cliques from another point of view. For a given
temporal graph G = (T, V, E) and a ∆ ∈ N, the static graph G∆
τ = (Vτ , Eτ )
describes all contacts that appear within the ∆-sized time window [τ, τ + ∆]
with τ ∈ [α, ω − ∆] in the temporal graph G, that is Vτ = V and for
every {v1 , v2 } ∈ Eτ there is a time step t ∈ [τ, τ + ∆] such that ({v1 , v2 }, t) ∈
E. The existence of a ∆-clique C = (X, I = [a, b]) indicates that all vertices
in X form a clique in all static graphs G∆
τ with τ ∈ [a, b − ∆]. This implies
that all vertices in X are pairwise connected to each other in the static
graphs of all sliding, ∆-sized time windows from time a until b − ∆.
By setting ∆ to the length of the whole lifetime of the temporal graph,
every ∆-clique corresponds to a normal clique in the underlying static graph
that results from ignoring the time stamps of the time-edges.
We are most interested in ∆-cliques that are not contained in any other
∆-clique. For this we also need to adapt the notion of maximality to the
temporal setting [28, 29]. Let G be a temporal graph. We call a ∆-clique C =
(X, I) in G vertex-maximal if we cannot add any vertex to X without having
to decrease the clique’s lifetime I. That is, there is no ∆-clique C 0 = (X 0 , I 0 )
in G with I ⊆ I 0 and X ( X 0 . We say that a ∆-clique is time-maximal if
we cannot increase the lifetime I without having to remove vertices from X.
That is, there is no ∆-clique C 0 = (X 0 , I 0 ) in G with I ( I 0 and X ⊆ X 0 .
We call a ∆-clique maximal if it is both vertex-maximal and time-maximal.
2.1.3

∆-Neighborhood, ∆-Cut, and other Temporal Graph Concepts

In this section, we introduce and define further graph theoretical concepts
that need to be adapted to the temporal setting.

5

We refer to a tuple (v, I = [a, b]) with v ∈ V and I ⊆ T as a vertexinterval pair of a temporal graph. We call a the starting point of interval I
and b the endpoint of interval I. Let X be a set of vertex-interval pairs.
The modified element relation (v, I) @
− X (temporal membership) expresses
that there exists a vertex-interval pair (v, I 0 ) ∈ X with I ⊆ I 0 .
Using these definitions, we can adapt the notion of a neighborhood of
a vertex to temporal graphs. Intuitively, we want that two vertex-interval
pairs are neighbors if they can be put into a ∆-clique together.
Definition 3 (∆-Neighborhood). For a vertex v ∈ V and a time interval I ⊆ T in a temporal graph, the ∆-neighborhood N ∆ (v, I) is the set
of all vertex-interval pairs (w, I 0 = [a0 , b0 ]) with the property that for every τ ∈ [a0 , b0 − ∆] at least one edge ({v, w}, t) ∈ E with t ∈ [τ, τ + ∆] exists.
Furthermore, b0 − a0 ≥ ∆, I 0 ⊆ I, and I 0 is maximal, that is, there is no
time interval I 00 ⊆ I with I 0 ⊂ I 00 satisfying the properties above.
Notice that being a ∆-neighbor of another vertex is a symmetric relation.
If (w, I 0 ) @
− N ∆ (v, I), then we say that w is a v∆-neighbor of v during the
time interval I 0 . In Figure 1, we visualize the concepts of ∆-neighborhood
and ∆-clique in a temporal graph. See also Example 1 below.
We need to define a suitable way of intersecting of two sets of vertexinterval pairs, so that, as the intuition suggests, a ∆-clique is just the intersection of the “closed” ∆-neighborhoods2 of its elements over the lifetime of
the clique.
Definition 4 (∆-Cut). Let X and Y be two sets of vertex-interval pairs.
The ∆-cut X uY contains for each vertex, all intersections of intervals in X
and Y that are of size at least ∆. More precisely,
X u Y = {(v, I ∩ I 0 ) | (v, I) ∈ X ∧ (v, I 0 ) ∈ Y ∧ |I ∩ I 0 | ≥ ∆}.
In other words, the ∆-cut X u Y contains all vertex-interval pairs (v, I)
such that (v, I) @
− X and (v, I) @
− Y , as well as |I| ≥ ∆, and I is maximal
under these properties. That is, there is no J with I ( J and J ⊆ I 0
and J ⊆ I 00 such that (v, I 0 ) @
− X and (v, I 00 ) @
− Y for some I 0 and I 00 .
Example 1. In Figure 1 we visualize a temporal graph and the concepts of
∆-neighborhood and ∆-clique. We consider a temporal graph G = (T, V, E)
with T = [0, 8], V = {a, b, c}, E = {({a, b}, 2), ({a, b}, 3), ({a, c}, 4), ({b, c}, 5),
({a, c}, 6)}, and ∆ = 2. The vertices are visualized as horizontal lines. The
connections between two vertices at a specific time step represent the timeedges of the temporal graph.
We visualize the ∆-neighborhood of each vertex of the temporal graph
over the whole time interval T in Figures 1(a)-1(c):
2

In static graphs, the closed neighborhood of a vertex includes the vertex itself.

6

0

1

2

3

4

5

6

7

8

5

6

7

8

5

6

7

8

5

6

7

8

a
b
c
(a) N ∆ (a, T )

0

1

2

3

4

a
b
c
(b) N ∆ (b, T )

0

1

2

3

4

a
b
c
(c) N ∆ (c, T )

0

1

2

3

4

a
b
c
(d) Maximal ∆-Clique ({a, b, c} , [3 , 5])

Figure 1: ∆-Neighborhoods and a ∆-clique of a temporal graph with ∆ = 2.
The lifetime of the graph is T = [0, 8]. The elements of the ∆-neighborhoods
in (a), (b), and (c) are shaded in yellow and green (hatched), respectively.
A maximal ∆-clique (d) is shaded in yellow.

• In Figure 1(a), we consider the ∆-neighborhood N ∆ (a, T ) of vertex
a during the whole time interval T . The yellow shaded bar marks
the vertex-interval pair (b, [0, 5]) ∈ N ∆ (a, T ). The vertex b is a ∆neighbor of a during [0, 5] because for every τ ∈ [0, 5 − ∆ = 3] at
7

least one time-edge ({a, b}, t) ∈ E with t ∈ [τ, τ + ∆] exists since
({a, b}, 2), ({a, b}, 3) ∈ E. The same holds for the vertex-interval pair
(c, [2, 8]) ∈ N ∆ (a, T ) which is marked in hatched green.
• In Figure 1(b), we visualize the ∆-neighborhood N ∆ (b, T ) of b over
the whole lifetime T of the temporal graph. The vertex-interval pair
(c, [3, 7]) ∈ N ∆ (b, T ) is marked in hatched green. The vertex-interval
pair (a, [0, 5]) ∈ N ∆ (b, T ) is shaded in yellow. It becomes evident that
being a ∆-neighbor of another vertex is a symmetric relation—if a
is a ∆-neighbor of b during [0, 5], then b is also a ∆-neighbor of a
during [0, 5].
• In Figure 1(c), we visualize the ∆-neighborhood N ∆ (c, T ) of c over
the whole lifetime T of the temporal graph. The vertex-interval pair
(b, [3, 7]) ∈ N ∆ (c, T ) is marked in hatched green. The vertex-interval
pair (a, [2, 8]) ∈ N ∆ (c, T ) is shaded in yellow.
Figure 1(d) shows the maximal ∆-clique ({a, b, c}, [3, 5]). During the time
interval [3, 5], a and b are ∆-neighbors, b and c are ∆-neighbors and a and c
are ∆-neighbors, see Figures 1(a)-1(c). We cannot increase the time interval
because at time step 2 the vertices b and c are not yet ∆-neighbors and at time
step 6 the vertices a and b are no longer ∆-neighbors. Further nontrivial
maximal ∆-cliques in this temporal graph are: ({a, b}, [0, 5]), ({a, c}, [2, 8]),
({b, c}, [3, 7]), as well as the trivial ∆-cliques ({a}, [0, 8]), ({b}, [0, 8]), and
({c}, [0, 8]).

2.2

Bron-Kerbosch Algorithm

In this section, we explain the basic idea of the (static) Bron-Kerbosch
algorithm. We also present two techniques known from the literature which
improve the running time of the algorithm.
The Bron-Kerbosch algorithm [3] enumerates all maximal cliques in undirected, static graphs. It is a widely used recursive backtracking algorithm
which is easy to implement and more efficient than alternative algorithms
in many practical applications [4].
The Bron-Kerbosch algorithm, see Algorithm 1, receives three disjoint
vertex-sets as an input: P , R, and X. The set R induces a clique and P ∪ X
is the set of all vertices which are adjacent to every vertex in R. Each vertex
in P ∪X is a witness that the clique R is not maximal yet. The set P contains
the vertices that have not been considered yet whereas the set X includes all
vertices that have already been considered in earlier steps. In each recursive
call, the algorithm checks whether the given clique R is maximal or not.
If P ∪ X = ∅, then there are no vertices that can be added to the clique
and therefore, the clique is maximal and can be added to the solution.
Otherwise, the clique is not maximal because at least one vertex exists that
8

Algorithm 1 Enumerating all Maximal Cliques
1: function BronKerbosch(P, R, X)
. R : a clique
. P ∪ X : set of all vertices v such that R ∪ {v} is a clique and where
• vertices in P have not yet been considered as additions to R and
• vertices in X already have been considered in earlier steps
2:
3:
4:
5:
6:
7:
8:
9:
10:

if P ∪ X = ∅ then
add R to the solution
end if
for v ∈ P do
BronKerbosch(P ∩ N (v), R ∪ {v}, X ∩ N (v)))
P ← P \ {v}
X ← X ∪ {v}
end for
end function

is adjacent to all vertices in R and consequently would form a clique with R.
For each v ∈ P the algorithm makes a recursive call for the clique R ∪ {v}
and restricts P and X to the neighborhood of v. After the recursive call,
vertex v is removed from P and added to X. This guarantees that the same
maximal cliques are not detected multiple times. For a graph G = (V, E)
the algorithm is initially called with P = V and R = X = ∅.
2.2.1

Pivoting

Bron and Kerbosch [3] introduced a method to increase the efficiency of
the basic algorithm by choosing a pivot element to decrease the number
of recursive calls. It is based on the observation that for any vertex u ∈
P ∪ X either u itself or one of its non-neighbors must be contained in any
maximal clique containing R. This is true since if neither u nor one of the
non-neighbors of u are included in a clique containing R, then this clique
cannot be maximal because u can be added to this clique due to the fact
that only neighbors of u were added to R. Hence, if we modify the BronKerbosch algorithm (Algorithm 1) so that we choose an arbitrary pivot
element u ∈ P ∪ X and iterate only over u and all its non-neighbors, then
we still enumerate all maximal cliques containing R but decrease the number
of recursive calls in the for-loop of Algorithm 1. Tomita et al. [25] have shown
that if u is chosen from P ∪ X such that u has the most neighbors in P , then
all maximal cliques of a graph G = (V, E) are enumerated in O(3|V |/3 ) time,
see Algorithm 2.

9

Algorithm 2 Enumerating all Maximal Cliques in a Graph with Pivoting
1: function BronKerboschPivot(P, R, X)
. R : a clique
. P ∪ X : set of all vertices v such that R ∪ {v} is a clique and where
• vertices in P have not yet been considered as additions to R and
• vertices in X already have been considered in earlier steps
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

if P ∪ X = ∅ then
add R to the solution
end if
choose pivot vertex u ∈ P ∪ X with |P ∩ N (u)| = max | P ∩ N (v) |
v∈P ∪X
for v ∈ P \ N (u) do
BronKerboschPivot(P ∩ N (v), R ∪ {v}, X ∩ N (v)))
P ← P \ {v}
X ← X ∪ {v}
end for
end function

2.2.2

Degeneracy of a Graph

Degeneracy is a measure of graph sparsity. Real-world instances of static
graphs (especially social networks) are often sparse, resulting in a small
degeneracy value [4]. This motivates a modification of the Bron-Kerbosch
algorithm which we present in this section and the complexity analysis of
this algorithm parameterized by the degeneracy of the input graph. The
degeneracy of a graph is defined as follows.
Definition 5 (Degeneracy). The degeneracy of a static graph G is defined
as the smallest integer d ∈ N such that each subgraph G0 of G contains a
vertex v with degree at most d.
If a graph has degeneracy d, we also call it d-degenerated. It is easy to
see that the maximal clique size of a d-degenerated graph is at most d + 1:
If there is a clique of size at least d + 2, then the vertices of this clique
would form a subgraph in which every vertex v of the clique has a degree
larger than d. For each d-degenerated graph there is a degeneracy ordering,
which is a linear ordering of the vertices with the property that for every
vertex v we have that at most d of its neighbors occur at a later position
in the ordering. The degeneracy d and a corresponding degeneracy ordering
for a graph G = (V, E) can be computed in linear time [4]: For graph G, the
vertex with the smallest degree is selected in each step and removed from
the graph until no vertex is left. The degeneracy of the graph is the highest
degree of a vertex at the time the vertex has been removed from the graph
and a corresponding degeneracy ordering is the order in which the vertices
were removed from the graph.
10

Algorithm 3 Enumerating all Maximal Cliques in a Graph with Degeneracy
Ordering
1: function BronKerboschDeg(P, R, X)
. R : a clique
. P ∪ X : set of all vertices v such that R ∪ {v} is a clique and where
• vertices in P have not yet been considered as additions to R and
• vertices in X already have been considered in earlier steps
2:
3:
4:
5:
6:
7:

for vi in a degeneracy odering v0 , v1 , . . . , vn of G = (V, E) do
P ← N (vi ) ∩ {vi+1 , . . . , vn−1 }
X ← N (vi ) ∩ {v0 , . . . , vi−1 }
BronKerboschPivot(P, {vi }, X)
end for
end function

For a graph G = (V, E) with degeneracy d, Eppstein et al. [4] showed
that using the degeneracy ordering of G in the outer-most recursive call and
afterwards using pivoting, all maximal cliques can be enumerated in O(d·|V |·
3d/3 ) time, see Algorithm 3. In other words, enumerating maximal cliques
is fixed-parameter tractable with respect to the parameter degeneracy d of
the input graph.

3

Bron-Kerbosch Algorithm for Temporal Graphs

We adapt the static Bron-Kerbosch algorithm to the temporal setting to enumerate all ∆-cliques, see Algorithm 4. The input of the algorithm consists
of two sets P and X of vertex-interval pairs as well as a tuple R = (C, I),
where C is a set of vertices and I a time interval. The idea is that in every recursive call of the algorithm, R is a time-maximal ∆-clique, and the
sets P and X contain vertex-interval pairs that are in the ∆-neighborhood
of every vertex in C during an interval I 0 ⊆ I. In particular, P ∪ X includes
all vertex-interval pairs (v, I) for which (C ∪ {v}, I) is a time-maximal ∆clique. While each vertex-interval pair in P still has to be combined with R
to ensure that every maximal ∆-clique will be found, for every vertexinterval pair (v, I 0 ) ∈ X every maximal ∆-clique (C 0 , I 00 ) with C ∪ {v} ⊆ C 0
and I 00 ⊆ I 0 has already been detected in earlier steps.
We show below that if ∀(w, I 0 ) ∈ P ∪ X : I 0 ( I, then there is no vertex v that forms a ∆-clique together with C over the whole time interval I.
Consequently, R = (C, I) is a maximal ∆-clique.
In one step, for every vertex-interval pair (v, I 0 ) ∈ P a recursive call is
initiated for the ∆-clique R0 = (C ∪ {v}, I 0 ) with all parameters restricted to
the ∆-neighborhood of v in the time interval I 0 , that is, P u N ∆ (v, I 0 ) and
X u N ∆ (v, I 0 ). For the set P 0 for example, we get a set of all time-maximal
11

Algorithm 4 Enumerating all Maximal ∆-Cliques
1: function BronKerboschDelta(P, R = (C, I), X)
. R = (C, I) : time-maximal ∆-clique
. P ∪ X : set of all vertex-interval pairs (v, I 0 ) such that I 0 ⊆ I and
(C ∪ {v}, I 0 ) is a time-maximal ∆-clique and where
• vertex-interval pairs in P have not yet been considered as additions
to R and
• vertex-interval pairs in X already have been considered in earlier
steps
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

if ∀(w, I 0 ) ∈ P ∪ X : I 0 ( I then
add R to the solution
end if
for (v, I 0 ) ∈ P do
R0 ← (C ∪ {v}, I 0 )
P 0 ← P u N ∆ (v, I 0 )
X 0 ← X u N ∆ (v, I 0 )
BronKerboschDelta(P 0 , R0 , X 0 )
P ← P \ {(v, I 0 )}
X ← X ∪ {(v, I 0 )}
end for
end function

vertex-interval pairs (w, I 00 ) for which it holds that (w, I 00 ) @
− N ∆ (v, I 0 ) and
00
(w, I ) @
− P . This restriction is made so that for all (w, I 00 ) ∈ P 0 of the
recursive call the vertex w is not only a ∆-neighbor of all x ∈ C but also of
the vertex v during the time I 00 ⊆ I 0 .
After the recursive call for ∆-clique (C ∪ {v}, I 0 ), the tuple (v, I 0 ) is
removed from the set P and added to the set X to avoid that the same
cliques are found multiple times.
For a temporal graph G = (V, E, T ) and a given time period ∆, the initial
call of Algorithm 4 to enumerate all maximal ∆-cliques in graph G is made
with P = {(v, T ) | v ∈ V }, R = (∅, T ) and X = ∅. In the remainder of this
document we will always assume that BronKerboschDelta is initially
called with those inputs.

3.1

Analysis

In the following, we prove the correctness of the algorithm and analyze its
running time. We start with arguing that the sets P and X behave as
claimed.
Lemma 1. For each recursive call of BronKerboschDelta
with R =
d
(C, I) and C 6= ∅, it holds that P ∪ X = v∈C N ∆ (v, I).
12

Proof. We prove this by induction on the recursion depth, that is, the number |C| of vertices in the clique in the current recursive call. In the initial call we have that C = ∅. In each iteration of the first call we have
that P ∪ X = {(v, T ) | v ∈ V } since, whenever a vertex-interval pair is
removed from P , then it is added to X, and initially P = {(v, T ) | v ∈ V }.
For every recursive call of BronKerboschDelta with R0 = (C 0 , I 0 ), P 0 ,
and X 0 , and C 0 = {v} for some vertex v we have that P 0 = P u N ∆ (v, I 0 )
and X 0 = X u N ∆ (v, I 0 ). Hence, we get
P 0 ∪ X 0 = {(v, T ) | v ∈ V } u N ∆ (v, I 0 ) = N ∆ (v, I 0 ).
Now we assume that we are in a recursive call of BronKerboschDelta
with R = (C, I), P , and
|C| > 1. By the induction hypothesis we
d X, where
∆
know that P ∪ X = v∈C N (v, I). Let (v, I 0 ) ∈ P be the vertex added to
the ∆-clique, that is, in the next recursive call we have that R0 = (C 0 , I 0 ),
with C 0 = C ∪ {v}, and P 0 = P u N ∆ (v, I 0 ) as well as X 0 = X u N ∆ (v, I 0 ).
Then,
P 0 ∪ X 0 = (P u N ∆ (v, I 0 )) ∪ (X u N ∆ (v, I 0 ))
= (P ∪ X) u N ∆ (v, I 0 )
l
=
N ∆ (w, I) u N ∆ (v, I 0 )
w∈C

=

l

N ∆ (w, I 0 ).

w∈C 0

This proves the claim.
Next, we show that the set R behaves as claimed, that is, R is indeed a
time-maximal ∆-clique in each recursive call of BronKerboschDelta.
Lemma 2. In each recursive call of BronKerboschDelta, R = (C, I) is
a time-maximal ∆-clique.
Proof. We show by induction on the recursion depth that R = (C, I) is
a time-maximal ∆-clique and that all vertex-interval pairs (v, I 0 ) in P are
∆-neighbors during I 0 to all vertices in the ∆-clique R and that I 0 is maximal under this property. The algorithm is initially called with R = (∅, T ),
which is a trivial time-maximal ∆-clique, and P = {(v, T ) | v ∈ V }, which
fulfills the desired property since the initial ∆-clique is empty and T is the
maximum time interval. In each recursive call BronKerboschDelta is
called with (P u N ∆ (v, I 0 ), (C ∪ {v}, I 0 ), X u N ∆ (v, I 0 )) for some (v, I 0 ) ∈ P .
By the induction hypothesis, v is a ∆-neighbor to all vertices in C during
time interval I 0 , and I 0 is maximal. Hence, (C ∪ {v}, I 0 ) is a time-maximal
∆-clique. Furthermore, each vertex-interval pair (v 0 , I 00 ) in P u N ∆ (v, I 0 ) is
in the ∆-neighborhood of each vertex-interval pair (v 00 , I 0 ) with v 00 ∈ C ∪{v},
13

since it is both in P and hence in the ∆-neighborhood of each vertex in C
and in N ∆ (v, I 0 ). The maximality of I 0 follows from the fact that the ∆-cut
and ∆-neighborhood operations preserve maximality of intervals by definition.
Now we can prove the correctness of the algorithm.
Theorem 1 (Correctness of Algorithm 4). Let G = (V, E, T ) be a temporal
graph. If algorithm BronKerboschDelta(P, R, X) is run on input (V ×
{T }, (∅, T ), ∅), then it adds all maximal ∆-cliques of G, and only these, to
the solution.
Proof. Let R∗ = (C ∗ , I ∗ ) be a maximal ∆-clique with |C ∗ | > 1. For a
recursive call of BronKerboschDelta on (P, R, X), say that a vertex is
a candidate, if there is an interval I with I ∗ ⊆ I such that (v, I) ∈ P . We
show by induction on |C ∗ | − `, that for each ` = 0, 1, . . . , |C ∗ | there is a
recursive call of BronKerboschDelta on (P, R = (C, I), X) with C ⊆ C ∗
and ` = |C ∗ \ C| candidates.
Clearly, in the initial call, C = ∅ ⊆ C ∗ and each vertex in C ∗ is a candidate. Now assume that there is a recursive call with (P, R = (C, I), X)
and C ⊆ C ∗ , and with ` − 1 = |C ∗ \ C| candidates. Consider the for-loop in
that recursive call and consider the first vertex-interval pair (v, I 0 ) in that
loop in which v is a candidate and I ∗ ⊆ I 0 . BronKerboschDelta proceeds
with a recursive call on (P u N ∆ (v, I 0 ), R0 = (C ∪ {v}, I 0 ), X u N ∆ (v, I 0 )).
Observe that each candidate except v remains a candidate also in this recursive call. Furthermore, |C ∗ \ (C ∪ {v})| = `. Thus, by induction there is a
recursive call with the sets (P, R, X) in which R∗ = R. Since
R∗ is maximal
d
00
by assumption, for each vertex-interval pair (w, I ) ∈ v∈C ∗ N ∆ (v, I ∗ ) we
have I 00 ( I ∗ . By Lemma 1 we have ∀(w, I 0 ) ∈ P ∪ X : I 0 ( I ∗ and hence,
R∗ is added to the solution.
Now assume that R = (C, I) is added to the solution. By Lemma 2, R
is a time-maximal ∆-clique. By Lemma 1 and since P ∪ X = ∅, there is no
vertex that can be added to R. Hence, R is a maximal ∆-clique.
Next, we analyze the running time of BronKerboschDelta. We start
with the following observation.
Lemma 3. For every time-maximal ∆-clique R of a temporal graph G =
(V, E, T ), there is at most one recursive call of BronKerboschDelta
with R as an input.
Proof. Assume that there are two recursive calls A and B of BronKerboschDelta with the same R = (C, I). Let R0 = (C 0 , I 0 ), with C 0 ⊂ C
and I ⊆ I 0 , occur in the recursive call corresponding to the closest common ancestor of the recursive calls A and B in the recursion tree. Hence,

14

there are two vertex-interval pairs (v, J), (w, J 0 ) ∈ P that lead to the calls A
and B, respectively, in the for loop.
Consider the case v = w. Then, J and J 0 must overlap in at least ∆
time steps, because I ⊆ J, J 0 ⊆ I 0 . However, P is contained in the ∆cut of the ∆-neighborhoods of C 0 over I 0 and thus, for each vertex no two
vertex-interval pairs in P overlap in ∆ time steps, a contradiction.
Now consider the case v 6= w. Without loss of generality due to symmetry assume that (v, J) is processed first in the for loop. Then, when
processing (w, J 0 ), pair (v, J) has been added to X. This is a contradiction
to the fact that recursive call B outputs R, that is, it outputs a clique with
time interval I ⊆ J.
Hence, we have that there cannot be two recursive calls of BronKerboschDelta with R = (C, I).
Now we upper-bound the running time for computing a ∆-cut.
Lemma 4. Let X and Y be two sets of vertex-interval pairs with the following properties.
• For every (v, I) ∈ X ∪ Y we have that |I| ≥ ∆,
• for every (v, I) ∈ X and (v, I 0 ) ∈ X we have that |I ∩ I 0 | < ∆,
• for every (v, I) ∈ Y and (v, I 0 ) ∈ Y we have that |I ∩ I 0 | < ∆,
• X and Y are sorted lexicographically by first the vertex and then the
starting point of the interval.
Then the ∆-cut X u Y can be computed in O(|X| + |Y |) time such that it is
also sorted lexicographically by first the vertex and then the starting point of
the interval.
Proof. The ∆-cut X u Y of two sets of vertex-interval pairs X and Y can
be computed in the following way.
For every vertex v, we do the following:
1. Select the first vertex-interval pairs (v, I) and (v, I 0 ) from X and Y ,
respectively.
2. If |I ∩ I 0 | > ∆, then add (v, I ∩ I 0 ) to the output (the ∆-cut). If the
endpoint of I 0 is smaller than the endpoint of I, then replace (v, I 0 )
with the next vertex-interval pair in Y , otherwise replace (v, I) with
the next vertex-interval pair in X.
3. Repeat Step 2 until all vertex-interval pairs containing vertex v are
processed.
Note that the intervals for each vertex v are added to the output in order
of their starting point. Furthermore, by construction of the algorithm we
have that for each (v, I) in the output, (v, I) is also in the ∆-cut X u Y . It
remains to show that for all (v, I) ∈ X and (v, I 0 ) ∈ Y with |I ∩ I 0 | ≥ ∆ we
have that (v, I ∩ I 0 ) is included in the output. Let I = [a, b] and I 0 = [a0 , b0 ].
At some point, the procedure processes in Step 2 for the first time one of
(v, I) ∈ X or (v, I 0 ) ∈ Y . Without loss of generality, let (v, I) ∈ X be
15

processed first. If at the same time also (v, I 0 ) ∈ Y is processed, clearly,
(v, I ∩ I 0 ) is added to the output, as required. Now assume that Step 2
processes some other vertex-interval pair (v, I 00 = [a00 , b00 ]) ∈ Y , a00 < a0 ,
together with (v, I) ∈ X. Since |I ∩ I 0 | ≥ ∆ and |I 0 ∩ I 00 | < ∆ we have
that b00 < b and hence, (v, I) is not replaced in this step. Consequently, the
procedure eventually adds (v, I ∩ I 0 ) to the output.
In each step of the procedure at least one new vertex-interval pair is
processed and each vertex-interval pair in X and Y is only processed once.
Hence, the running time is in O(|X| + |Y |).
Lemmata 3 and 4 allow us to upper-bound the running time of BronKerboschDelta depending on the number of different time-maximal ∆-cliques
of the input graph.
Theorem 2. Let G = (V, E, T ) be a temporal graph with x distinct timemaximal ∆-cliques. Then BronKerboschDelta enumerates all maximal
∆-cliques in O(x · |E| + |E| · |T |) time.
Proof. We assume that all edges of the temporal graph are sorted by their
time stamp. Note that this can be done in a preprocessing step in O(|E|·|T |)
time using Counting Sort. Furthermore, we assume that for each vertex v,
the ∆-neighborhood N ∆ (v, T ) is given. These neighborhoods can be precomputed in O(|E|) time, assuming that the edges are sorted by their time
stamps.
By Lemma 3 we know that for each time-maximal ∆-clique there is at
most one recursive call of BronKerboschDelta. By charging the computation of P 0 , R0 , and X 0 to the corresponding recursive call, for each recursive
call we compute a constant number of ∆-neighborhoods and ∆-cuts. The
size of the sets P , X, and any ∆-neighborhood is upper-bounded by |E|
and each of these sets has the property that for every (v, I) and (v, I 0 ) out
of the same set we have that |I ∩ I 0 | < ∆. Given N ∆ (v, T ), N ∆ (v, I) can
be computed in O(|E|) time for any I and by Lemma 4, a ∆-cut can be
computed in O(|E|) time. Hence, all maximal ∆-cliques can be enumerated
in O(x · |E| + |E| · |T |) time.
We now use a general upper bound for the number of time-maximal ∆cliques in a temporal graph to bound the overall running time of BronKerboschDelta.
Corollary 1. Let G = (V, E, T ) be a temporal graph. BronKerboschDelta
enumerates all maximal ∆-cliques of G in O(2|V | · |T | · |E|) time.
Proof. Note that the vertex set of each maximal ∆-clique induces a static
clique in the static graph G underlying G that has an edge between two
vertices if and only if there is a time-edge in G between these vertices at
some time step. Furthermore, for each clique in G, there are at most |T |
16

maximal ∆-cliques because their time intervals are pairwise not contained in
one-another. Hence, the number of time-maximal ∆-cliques of any temporal
graph is upper-bounded by 2|V | ·|T |. By Theorem 2, we get an overall running
time in O(2|V | · |T | · |E|).

3.2

Pivoting

In this section, we explain how we can decrease the number of recursive
calls of BronKerboschDelta by using pivoting. Recall that the idea of
pivoting in the classic Bron-Kerbosch algorithm for static graphs is based
on the observation that for any vertex u ∈ P ∪ X either u itself or one of
its non-neighbors must be contained in any maximal clique containing R.
Vertex u is also called pivot.
A similar observation holds for maximal ∆-cliques in temporal graphs.
Instead of vertices, however, we now choose vertex-interval pairs as pivots:
For any (vp , Ip ) ∈ P ∪ X and any maximal ∆-clique Rmax = (Cmax , Imax )
with Imax ⊆ Ip , either vertex vp or one vertex w 6= vp which is not a ∆neighbor of vp during the time Imax , that is, (w, Imax ) 6@
− N ∆ (vp , Ip ), must
be contained in Cmax .
By choosing a pivot element (vp , Ip ) ∈ X ∪P we only have to iterate over
all elements in P which are not in the ∆-neighborhood of the pivot element,
see Algorithm 5. In other words, we do not have to make a recursive call
for any (w, I 0 ) ∈ P which holds (w, I 0 ) @
− N ∆ (vp , Ip ).
In Figure 2 we give an illustrative example for pivoting. In this example, we assume that the algorithm runs on a temporal graph such that the
set P = {(a, [0, 8]), (b, [0, 4]), (c, [1, 3]), (c, [5, 8])} occurs within a recursive
call of BronKerboschDeltaPivot. For simplicity, we show in Figure 2(a)
only the subgraph containing the elements of P and the relation between
these elements rather than displaying the whole graph. In Figure 2(b), we
choose element (a, [0, 8]) (hatched) as pivot. It can be seen that the elements (b, [0, 4]) and (c, [5, 8]) lie completely in the ∆-neighborhood (dotted)
of the pivot, that is, (b, [0, 4]), (c, [5, 8]) @
− N ∆ (a, [0, 8]). These two elements
can therefore be left out in the iteration over the elements in P of the
BronKerboschDelta. We only have to iterate over the pivot (a, [0, 8])
and the element (c, [1, 3]) which is not completely in the ∆-neighborhood
of our chosen pivot. In Figure 2(c), we can see that for every maximal
∆-clique (C, I) with respect to P either a ∈ C, I ⊆ [0, 8] or c ∈ C,
I ⊆ [1, 3]. The figure hence shows that iterating over the elements (b, [0, 4])
and (c, [5, 8]) will not find any maximal ∆-clique that we do not find via one
of the elements (a, [0, 8]) and (c, [1, 3]).
Next, we formally prove the correctness of this procedure.
Proposition 1. For each ∆-clique R = (C, I) and a pivot element (vp , Ip ) ∈
P ∪ X, the following holds: for every Rmax = (Cmax , Imax ) with C ⊂ Cmax

17

0

1

2

3

4

5

6

7

8

a
b
c
(a) P = {(a, [0, 8]), (b, [0, 4]), (c, [1, 3]), (c, [5, 8])}

0

1

2

3

4

5

6

7

8

a
b
c
(b) Pivot (a, [0, 8]) with (b, [0, 4]), (c, [5, 8]) ∈ N ∆ (a, [0, 8])

0

1

2

3

4

5

6

7

8

a
b
c
(c) ∆-cliques

Figure 2: A exemplary set P of BronKerboschDeltaPivot, a possible pivot element (hatched) including its ∆-neighborhood (dotted), and all
maximal ∆-cliques with respect to set P , ∆ = 2.

and Imax ⊆ Ip ⊆ I it either holds that vp ∈ Cmax or otherwise there is a
vertex w ∈ Cmax that satisfies (w, I 0 ) ∈ P ∪ X, Imax ⊆ I 0 , and (w, Imax ) 6@
−
N ∆ (vp , Ip ), and consequently (w, I 0 ) 6@
− N ∆ (vp , Ip ).
Proof. Let Rmax = (Cmax , Imax ) be a maximal ∆-clique with C ⊂ Cmax
and Imax ⊆ Ip ⊆ I. Assume that vp ∈
/ Cmax and for each w ∈ Cmax it holds
that (w, Imax ) @
− N ∆ (vp , Ip ). Consequently, for each w ∈ Cmax \ C there
exists a (w, I 0 ) ∈ P ∪ X with Imax ⊆ I 0 . Because vp is a ∆-neighbor of all
vertices in Cmax \ C at least during Imax and a ∆-neighbor of all vertices
in C during Ip , the vertex vp can be added to the ∆-clique Rmax , yielding
another ∆-clique with at least the same lifetime. This is a contradiction to
the assumption that Rmax is maximal.
18

Algorithm 5 Enumerating all Maximal ∆-Cliques in a Temporal Graph
with Pivoting
1: function BronKerboschDeltaPivot(P, R = (C, I), X)
. R = (C, I) : time-maximal ∆-clique
. P ∪ X : set of all (v, I 0 ) s.t. I 0 ⊆ I and (C ∪ {v}, I 0 ) is a time-maximal
∆-clique
2:
if ∀(w, I 0 ) ∈ P ∪ X : I 0 ( I then
3:
add R to the solution
4:
end if
5:
choose pivot element (vp , Ip ) ∈ P ∪ X
6:
for (v, I 0 ) ∈ P \ {(w, I 00 ) | (w, I 00 ) ∈ P ∧ (w, I 00 ) @
− N ∆ (vp , Ip )} do
0
0
7:
R ← (C ∪ {v}, I )
8:
P 0 ← P u N ∆ (v, I 0 )
9:
X 0 ← X u N ∆ (v, I 0 )
10:
BronKerboschDeltaPivot(P 0 , R0 , X 0 )
11:
P ← P \ (v, I 0 )
12:
X ← X ∪ (v, I 0 )
13:
end for
14: end function
An optimal pivot element is chosen in such a way that it minimizes the
number of recursive calls. It is the element in the set P ∪ X having the
largest number of elements in P in its ∆-neighborhood. We have seen that
the whole procedure is quite similar to pivoting in the basic Bron-Kerbosch
algorithm but with one difference: we are able to choose more than one
pivot element. The only condition that has to be satisfied is that the time
intervals of the pivot elements cannot overlap:
For each ∆-clique R = (C, I) in a recursive call of the algorithm, choosing
a pivot element (vp , Ip ) ∈ P ∪ X only affects maximal ∆-cliques Rmax =
(Cmax , Imax ) fulfilling Imax ⊆ Ip . Moreover, for all elements (w, I 0 ) ∈ P
satisfying (w, I 0 ) @
− N ∆ (vp , Ip ) it holds I 0 ⊆ Ip . Consequently, a further pivot
0
0
element (vp , Ip ) ∈ P ∪ X fulfilling that Ip0 does not overlap with Ip neither
interferes with the considered maximal ∆-cliques nor with the vertex-interval
pairs in P that are in the ∆-neighborhood of the pivot element (vp , Ip ).
The problem of finding the optimal set of pivot elements in P ∪ X can
be formulated as a weighted interval scheduling maximization problem:
Weighted Interval Scheduling
Input: A set J of jobs j with a time interval Ij and a weight wj
each.
P
Task: Find a subset of jobs J 0 ⊆ J that maximizes j∈J 0 wj such
that for all i, j ∈ J 0 with i 6= j, the time intervals Ii and Ij do
not overlap.
In our problem, the jobs are the elements of P ∪ X and the weight of an
19

element is thereby the number of all elements that are in P and lie in the ∆neighborhood of this element. Formally, the jobs are the elements (v, I 0 ) ∈
P ∪X, the corresponding time interval is I 0 of the element (v, I 0 ) and the corresponding weight w(v,I 0 ) = |{(v, I) | (v, I) ∈ P ∧ (v, I) @
− N ∆ (v, I 0 )}|. This
problem can be solved efficiently in O(min(|E|, |V | · |T |) · log(min(|E|, |V | ·
|T |))) time by using dynamic programming [15, Chapter 6.1] under the assumption that the weights of the potential pivot elements are known.

4

Degeneracy of Temporal Graphs

Recall from Section 2.2.2 that one can upper-bound the running time of the
static Bron-Kerbosch algorithm using the degeneracy of the input graph.
The degeneracy of a graph G is the smallest integer d such that every nonempty subgraph of G contains a vertex of degree at most d. We now give an
analogue for the temporal setting, motivated by the fact that static graphs
are often sparse in practice as measured by small degeneracy [4]. Intuitively,
we want to capture the fact that a temporal graph keeps its degeneracy value
during its whole lifetime.
Definition 6 (∆-slice degeneracy). A temporal graph G = (V, E, T ) has
∆-slice degeneracy d if for all t ∈ T we have that the graph Gt = (V, Et ),
where Et = {{v, w} | ({u, w}, t0 ) ∈ E for some t0 ∈ [t, t+∆]}, has degeneracy
at most d.
Using the parameter ∆-slice degeneracy, we can upper-bound the number
of time-maximal ∆-cliques of a temporal graph.
Lemma 5. Let G = (V, E, T ) be a temporal graph with ∆-slice degeneracy d.
Then, the number of time-maximal ∆-cliques in G is at most 3d/3 · 2d+1 ·
|V | · |T |.
Proof. Let G = (V, E, T ) be a temporal graph with ∆-slice degeneracy d.
Then we call the graph Gt = (V, Et ), where Et = {{v, w} | ({u, w}, t0 ) ∈
E for some t0 ∈ [t, t + ∆]} a ∆-slice of G at time t. The vertex set of each
time-maximal ∆-clique which starts at time t is also a clique in Gt , otherwise
there would be two vertices which are disconnected for more than ∆ timesteps. Since Gt has degeneracy at most d, the number of maximal cliques
of Gt is upper-bounded by 3d/3 · |V | [4]. Furthermore, the maximum size of
a clique is upper-bounded by d + 1. Hence, the total number of cliques is
upper-bounded by 3d/3 · 2d+1 · |V |. Note that for each of those cliques we
have at most one time-maximal ∆-clique starting at time t. Hence, the total
number of ∆-cliques is at most 3d/3 · 2d+1 · |V | · |T |.
Lemma 5 now allows us to bound the running time of Algorithm 4 using
the ∆-slice degeneracy d of the input graph G.
20

Theorem 3. Let G = (V, E, T ) be a temporal graph with ∆-slice degeneracy d. Then, BronKerboschDelta enumerates all ∆-cliques of G in
O(3d/3 · 2d · |V | · |T | · |E|) time.
Proof. By Lemma 5 we know that the number of time-maximal ∆-cliques in
a temporal graph with ∆-slice degeneracy d is at most 3d/3 · 2d+1 · |V | · |T |.
Hence, by Theorem 2, we get an overall running time in O(3d/3 · 2d · |V | ·
|T | · |E|).
Note that Theorem 3 implies that enumerating all maximal ∆-cliques is
fixed-parameter tractable with respect to the parameter ∆-slice degeneracy.
Hence, while NP-hard in general, the problem can be solved efficiently if the
∆-slice degeneracy of the input graph is small.

5

Experimental Results

In this section we present our experimental results. We give the ∆-slice degeneracy of several real-world temporal graphs for several values for ∆. Then
we show the behavior of our implementation of BronKerboschDeltaPivot
(Algorithm 5) applied to these real-world temporal graphs and compare it
to the algorithm implemented by Viard et al. [29].

5.1

Setup and Statistics

We now give details of the implementation and the used reference algorithm,
and introduce the data sets we used in the experiments. Furthermore, we
explain how the values of ∆ were chosen, give some statistics for the data
set, and calculate the ∆-slice degeneracy of the data sets for the chosen
values of ∆.
Implementation. We implemented3 BronKerboschDeltaPivot with
slight modifications that allow the algorithm to use multiple pivot elements
(we refer to this version as BronKerboschDeltaPivot*). Furthermore,
we implemented a simple algorithm to compute the ∆-slice degeneracy.
Both implementations are in Python 2.7.12 and all experiments were carried
out on an Intel Xeon E5-1620 computer with four cores clocked at 3.6 GHz
and 64 GB RAM. We did not utilize the parallel-processing capabilities although it should be easy to achieve almost linear speed-up with growing
number of cores due to the simple nature of BronKerboschDeltaPivot.
The operating system was Ubuntu 16.04.4 with Linux kernel version 4.4.057. We compared BronKerboschDeltaPivot* with the algorithm by
Viard et al. [29] which was also implemented in Python. We modified their
3

Code freely available at http://fpt.akt.tu-berlin.de/temporalcliques/ (GNU
General Public License).

21

source code4 by removing the text output in their implementation in order
to avoid speed differences. We call their algorithm Algorithm VLM below.
Data Sets. We chose several freely available real-world temporal graphs
aiming for an overview over the different kinds of contexts in which such
graphs arise, that is, an overview over different modes of communication and
different kinds of entities and environments in which this communication
takes place. However, a focus is on temporal graphs based on physical
proximity of individuals, since previous work on ∆-cliques also focused on
these [28, 29]. The contexts and sources of our test set of temporal graphs
are as follows:
• internet-router communication: as733 [18],
• email communication: karlsruhe [7],
• social-network communication: facebook-like [23], and
• physical-proximity5 between
– high school students: highschool-2011, highschool-2012, highschool2013 [1, 6, 24],
– patients and health-care workers: hospital-ward [27],
– attendees of the ACM Hypertext 2009 conference: hypertext [13],
– attendees of the Infectious SocioPatterns event: infectious [13],
and
– children and teachers in a primary school: primaryschool [24].
Table 1 contains the number of vertices, edges, temporal resolution, and
lifetime of the corresponding temporal graphs. As a time step we fixed one
second for each of the data sets. Viard et al. [29], as the first work on enumerating ∆-cliques, used the data set highschool-2012 in their experiments.
Chosen values of ∆. In order to limit the influence of time scales in the
data and to make running times comparable between instances, as well as
to be able to present the results in a unified way, we chose the ∆-values as
follows. We decided on a reference point of the edge appearance rate that
is, of the average number of edges per time step and we fixed a set of ∆values for this reference point. For each considered instance we then scaled
the reference ∆-values proportionally to the quotient of the reference edge
appearance rate and the edge appearance rate in the instance.
4
5

Code freely available at https://github.com/TiphaineV/delta-cliques .
Available at http://www.sociopatterns.org/datasets .

22

Table 1: Statistics for the data sets used in our experiments.
Instance
as733
facebook-like
highschool-2011
highschool-2012
highschool-2013
hospital-ward
hypertext
infectious
karlsruhe
primaryschool

Vertices

Edges

Resolution

Lifetime (s)

7,716
1,899
126
180
327
75
113
10,972
1,870
242

11,410,810
59,835
28,560
45,047
188,508
32,424
20,818
415,912
461,661
125,773

1d
1s
20s
20s
20s
20s
20s
20s
1s
20s

67,824,000
16,736,181
272,330
729,500
363,560
347,500
212,340
6,946,340
123,837,267
116,900

As the reference point we chose the edge appearance rate of 1/5 edges per
time step; this value was chosen for convenience within the interval of edgeappearance rates in the studied data sets (see Table 1). Since, intuitively, the
∆-values of interest in practice increase exponentially, we chose as reference
∆-values the numbers 0 and 5i for i = 1, 2, . . .. As mentioned, for each
instance, these values are then multiplied by the quotient of edge appearance
rates. That is, if the instance has m edges and lifetime `, then we scaled
the reference ∆-values by the factor (1/5)/(m/`) = `/(5m). For example,
for highschool-2012 we obtain the ∆-values {0, 80, 404, 2024, 10121, 50606,
253034, . . .}. For reference, recall that each time step in highschool-2012
corresponds to one second (a day has 86,000 seconds and a week has 604,800
seconds). In figures, we refer to each scaled value of ∆ by ∆ ∼ 5i for some
concrete i. Viard et al. [28] used ∆-values according to 60 seconds, 15
minutes, 1 hour and 3 hours.
∆-Slice Degeneracy. The ∆-slice degeneracies for our set of instances are
shown in Table 2 together with the static degeneracy of the underlying static
graph which has an edge whenever there is an edge at some time step in
the temporal graph. Clearly, as the value of ∆ increases, the ∆-slice degeneracy approaches—and is upper-bounded by—the static degeneracy. The
static degeneracy of our instances is small in comparison with the size of the
graph. This falls in line with the analysis by Eppstein et al. [4] for many
real-world graphs. Moreover, for many practically relevant values of ∆ the
∆-slice degeneracy is still significantly smaller. For example, in the instance
highschool-2012, the scaled value of ∆ corresponding to 53 equals 2204 time
steps (seconds) and the corresponding ∆-slice degeneracy is 5. This indicates that ∆-slice degeneracy can be a very promising (that is, also small)
parameter when designing and analyzing algorithms for temporal graphs.
We computed the ∆-slice degeneracies using a straightforward approach.
23

Table 2: Static degeneracy and ∆-slice degeneracy. Empty cells indicate
that the lifetime of the temporal graph is smaller than the scaled ∆-value.
Instance
as733
facebook-like
highschool-2011
highschool-2012
highschool-2013
hospital-ward
hypertext
infectious
karlsruhe
primaryschool

Static

∆=0

∼ 53

∼ 55

∼ 57

∼ 59

24
20
21
18
24
22
28
18
33
47

13
1
4
4
4
4
6
4
2
4

13
3
7
5
5
6
7
9
6
4

14
6
11
6
9
11
8
18
9
10

15
19
19
12
14
18
22
18
17
31

24

18
32

We iteratively computed for each ∆-long time interval the graph induced by
the edges in that time interval. For each of these graphs we computed
the static degeneracy using an implementation from the NetworkX python
library [8]. This approach is rather inefficient. For example, it took about
seven hours to compute the ∆-slice degeneracy for karlsruhe with ∆ ∼ 55
(equating to a ∆ value of about two hours).

5.2

Results and Running Times

We now study the efficiency of BronKerboschDeltaPivot*, evaluate
pivoting strategies, and compare the result to Algorithm VLM.
Pivoting. Generally we observed that pivoting plays a negligible role when
∆ is small compared to the overall lifetime of the graph, that is, when ∆ is
less than roughly one third of the lifetime. In this case, pivoting has almost
no effect on the running time and the number of recursive calls. For larger
values of ∆, however, pivoting can make a clear difference depending on the
type of temporal graph.
We tested five strategies for selecting a set of pivots from P in BronKerboschDeltaPivot*. Call a set of pivots is maximal if the interval of each
element from P overlaps with at least one pivot. We tested the following
variants of pivot sets:
1A) a single arbitrary pivot,
1G) a single pivot maximizing the number of elements removed from P ,
MA) an arbitrary maximal set of pivots (pivots picked one-by-one arbitrarily),
24

No Pivoting
1A
1G
MA
MG
MM

Running time (s)

30

20

10

0

0

2

4
∆

6
·105

Figure 3: Running time for different pivoting strategies on highschool-2012.
MG) a maximal set of pivots (pivots picked one by one according to the
maximum number of further elements removed from P ), and
MM) a set of pivots which maximizes the number of elements removed
from P .
Clearly, each strategy has its own trade-off between the time needed to
compute the pivots and the possible reduction in recursive calls.
Running times are given for highschool-2012 in Figure 3 with ∆ between 15,000 and 725,000. We note that running times for some very small
values of ∆ below 15,000 are larger than 30 s and hence do not fit in the
chart. We consider this phenomenon more closely below. For ∆ ≤ 15,000
there is no appreciable difference between the pivoting strategies. In terms
of relative difference between pivoting strategies, highschool-2012 seems to
be a representative example. Strategies 1G and MG seem to be the best options: they do not incur much overhead compared to no pivoting for small ∆
and yield strong running time improvements for larger ∆. In comparison
to no pivoting, strategies 1G and MG achieve a 60 % reduction in recursive
calls for ∆-values of around 7 · 106 in highschool-2012. Since the running
times of strategy 1G and MG are so close to each other we conclude that
in most cases there is only one important pivot that should be selected.
We were surprised to see that maximizing the overall number of elements
removed from P via the pivot set (strategy MM) results in slightly worse
running times and slightly larger numbers of recursive calls. The number
of elements that are removed by a pivot in one recursive call of the algorithm ranges between one and 14 while many of the calls remove two to four
elements. Notice that occasional reduction by ten or more elements can
25

No Pivoting
1A
1G
MA
MG
MM

Running time (s)

50

45

40

0

0.5

1
∆

1.5

2
·107

Figure 4: Running time for different pivoting strategies on facebook-like.
substantially decrease the search space, because in general its size depends
exponentially on the size of P .
Figure 4 shows running times for facebook-like. On this graph, pivoting
seldom removes more than one element from the candidate set P in one call
of the recursive procedure. Hence, for this instance, pivoting mainly incurs
overhead for computing the pivots, but do not substantially decrease the
search space. We consequently observe about 10 % slower running times,
regardless of the pivoting strategy.
In conclusion, strategy 1G offers the best trade-off between additional
running time spent with computing the pivot(s) and running time saved due
to decreased number of recursive calls. Overall, the the possible benefits
seem to outweigh the overhead incurred by pivoting on some instances. All
remaining experiments were thus carried out with strategy 1G.
Running Times and Comparison with Algorithm VLM. We experimented with BronKerboschDeltaPivot* (Algorithm 5) using pivoting strategy 1G and with Algorithm VLM for ∆ = 0 and ∆ ∼ 5i with
i = 1, 3, 5, 7, 9 (where the lifetime allowed such values of ∆). An excerpt of
the results is given in Table 3. Clearly, larger instances with more vertices
or edges demand a longer running time. However, even large instances like
infectious can still be solved within one hour.
From our theoretical results in Section 3 we expected that the running
time of BronKerboschDeltaPivot* increases exponentially with growing ∆-slice degeneracy. As the ∆-slice degeneracy grows very slowly with
increasing ∆ (see Table 2), we expected a corresponding moderate growth in
running time with respect to ∆. For larger ∆, this is consistent with the ex-

26

Table 3: ∆-clique statistics and running times: |C| denotes the number of
maximal ∆-cliques, s denotes the maximum ∆-clique size, ` the maximum
∆-clique lifetime divided by 105 , tBKD and tVLM denote the running time
in seconds of BronKerboschDelta* and Algorithm VLM, respectively.
Empty cells represent an exceeded running time limit of one hour.
∆=0
Instance
facebook-like
highschool-2011
highschool-2012
highschool-2013
hospital-ward
hypertext
infectious
karlsruhe
primaryschool

|C|

s

`

tBKD

tVLM

61,648
26,510
42,285
172,362
27,910
19,150
349,787

2
5
5
5
5
6
5

1,674
27
73
36
35
21
695

169
131
248
1,952
370
85
1,530

107,121

5

12

995

12
7
12
118
14
5
2,515
1,494
147

∆ ∼ 53
Instance
facebook-like
highschool-2011
highschool-2012
highschool-2013
hospital-ward
hypertext
infectious
karlsruhe
primaryschool

|C|

s

`

tBKD

tVLM

33,876
7,394
9,501
57,121
8,694
6,345
134,787

4
7
6
6
7
7
9

1,675
27
73
36
35
21
695

70
5
8
178
15
8
1,195

1,141
153
236
1,990
226
107

83,314

9

12

83

∆ ∼ 55
Instance
facebook-like
highschool-2011
highschool-2012
highschool-2013
hospital-ward
hypertext
infectious
karlsruhe
primaryschool

|C|

s

`

tBKD

23,247
7,760
7,536
29,752
10,869
7,459
163,162
235,684
508,430

5
10
7
8
12
7
16
9
20

1,709
28
75
37
36
23
697
12,417
15

47
4
4
23
7
4
1,277
1,235
890

27

tVLM

1,365

2,193

Running time (s)

103

BronKerboschDeltaPivot*
Algorithm VLM

102

101

102

103

104

∆

Figure 5: Running time vs. ∆ on highschool-2012.
perimental results, as shown in Figures 3, 4 and Table 3. However, for (very)
small ∆ we often observe an initial spike in the running time (and number of
∆-cliques) which then subsides. This is also shown in Figure 5. A possible
explanation for this spike is that, for small ∆, the ∆-neighborhood of many
vertices becomes very fragmented, leading to large candidate sets P in the
algorithm (although the size of P is still linear in the input size for constant
∆-slice degeneracy). Furthermore, if ∆ is small, then many singleton edges
may form maximal ∆-cliques themselves. These ∆-cliques then get taken
up into larger maximal ∆-cliques when ∆ increases, which decreases the
number of ∆-cliques and running times for BronKerboschDeltaPivot*.
On facebook-like our algorithm notably is comparably efficient given the
relatively large size (see Figures 4 and 6). Furthermore, the number of
∆-cliques does not seem to vary strongly with changing values of ∆. These
two facts may hint at some special structure that is present in temporal
graphs based on online social networks, in addition to small ∆-slice degeneracy.
Algorithm VLM is usually faster than BronKerboschDeltaPivot*
for small values of ∆ below the ∆ ∼ 53 threshold. Starting from there,
however, BronKerboschDeltaPivot* outperforms Algorithm VLM with
running times smaller by at least one order of magnitude and up to three
orders of magnitude (see Table 3). In terms of main memory, 385 MB is
the maximum used by BronKerboschDeltaPivot* over all solved instances, attained on infectious for ∆ = 0. On this instance, Algorithm VLM
uses 494 MB and often more than 1 GB.
Finally we mention that, when increasing the time limit to six hours,
BronKerboschDeltaPivot* can solve all instances of karlsruhe for ∆ = 0

28

Running time (s)

BronKerboschDeltaPivot*
Algorithm VLM

103

102
103

104
∆

Figure 6: Running time vs. ∆ on facebook-like.
and ∆ ∼ 5i for i = 1, 3, 5, 7, 9 wherein the last value of ∆ involves enumerating 43 · 106 maximal ∆-cliques.

6

Conclusion and Outlook

We studied the algorithmic complexity of enumerating ∆-cliques in temporal graphs. We adapted the Bron-Kerbosch algorithm ([3]), including the
procedure of pivoting to reduce the number of recursion calls, to the temporal setting and provided a theoretical analysis. For the theoretical analysis,
we formalized and employed the concept of ∆-slice degeneracy which may
be a useful parameter when analyzing problems in sparse temporal graphs.
In experiments on real-world data sets, we showed that our algorithm is
notably faster than the first approach for enumerating all maximal ∆-cliques
in temporal graphs due to Viard et al. [28, 29]. Our experimental results
further reveal that pivoting can notably decrease the running time for large
values of ∆. Furthermore, we measured the ∆-slice degeneracy for different
∆-values and showed that it is reasonably small in many real-world data
sets.
As to future research, an algorithmic challenge is to find a more efficient
way to compute the ∆-slice degeneracy of a given temporal graph, perhaps
via different characterizations as in the case of static graphs. See [4] for an
account of several equivalent definitions of the degeneracy of a static graph.
Regarding the adapted version of the Bron-Kerbosch algorithm, our theoretical analysis (based on the ∆-slice degeneracy parameter) of the running
time still leaves room for improvement. In particular, we leave the impact
of pivoting on the running time upper bound as an open question for future
29

research. It furthermore makes sense to try and implement further improved
branching rules on top of pivoting. This was also successful for the static
Bron-Kerbosch algorithm [21]. Another interesting question is whether an
analogue to the degeneracy ordering can be defined in the temporal setting
and, if so, whether it can be used to further improve the algorithm.
Acknowledgements. Anne-Sophie Himmel, Hendrik Molter and Manuel
Sorge were partially supported by DFG, project DAPA (NI 369/12). Manuel
Sorge gratefully acknowledges support by the People Programme (Marie
Curie Actions) of the European Union’s Seventh Framework Programme
(FP7/2007-2013) under REA grant agreement number 631163.11 and by
the Israel Science Foundation (grant no. 551145/14).
We are grateful to two anonymous SNAM reviewers whose feedback
helped to significantly improve the presentation and to eliminate some bugs
and inconsistencies.

References
[1] A. Barrat and J. Fournet. Contact patterns among high school students.
PLoS ONE, 9(9):e107878, 2014.
[2] S. Boccaletti, G. Bianconi, R. Criado, C. I. Del Genio, J. GómezGardeñes, M. Romance, I. Sendiña-Nadal, Z. Wang, and M. Zanin.
The structure and dynamics of multilayer networks. Physics Reports,
544(1):1–122, 2014.
[3] C. Bron and J. Kerbosch. Algorithm 457: finding all cliques of an
undirected graph. Communications of the ACM, 16(9):575–577, 1973.
[4] D. Eppstein, M. Löffler, and D. Strash. Listing all maximal cliques in
large sparse real-world graphs in near-optimal time. ACM Journal of
Experimental Algorithmics, 18(3):3.1:1–3.1:21, 2013.
[5] T. Erlebach, M. Hoffmann, and F. Kammer. On temporal graph exploration. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), volume 9134 of
LNCS, pages 444–455. Springer, 2015.
[6] V. Gemmetto, A. Barrat, and C. Cattuto. Mitigation of infectious disease at school: targeted class closure vs school closure. BMC Infectious
Diseases, 14(1):1, 2014.
[7] R. Goerke. Email network of KIT informatics. http://i11www.iti.
uni-karlsruhe.de/en/projects/spp1307/emaildata, 2011.

30

[8] A. A. Hagberg, D. A. Schult, and P. J. Swart. Exploring network
structure, dynamics, and function using NetworkX. In Proceedings of
the 7th Python in Science Conference (SciPy 2008), pages 11–15, 2008.
[9] A.-S. Himmel.
Enumerating maximal cliques in temporal graphs.
Bachelorthesis, TU Berlin, January 2016.
URL
http://fpt.akt.tu-berlin.de/publications/theses/
BA-anne-sophie-himmel.pdf. Bachelor thesis.
[10] A.-S. Himmel, H. Molter, R. Niedermeier, and M. Sorge. Enumerating maximal cliques in temporal graphs. In Proceedings of the 2016
IEEE/ACM International Conference On Advances in Social Networks
Analysis and Mining (ASONAM 2016), pages 337–344. IEEE, 2016.
[11] P. Holme and J. Saramäki. Temporal networks. Physics Reports, 519
(3):97–125, 2012.
[12] F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier. Isolation
concepts for clique enumeration: Comparison and computational experiments. Theoretical Computer Science, 410(52):5384–5397, 2009.
[13] L. Isella, J. Stehlé, A. Barrat, C. Cattuto, J.-F. Pinton, and W. Van den
Broeck. What’s in a crowd? Analysis of face-to-face behavioral networks. Journal of Theoretical Biology, 271(1):166–180, 2011.
[14] H. Ito and K. Iwama. Enumeration of isolated cliques and pseudocliques. ACM Transactions on Algorithms, 5(4):40, 2009.
[15] J. Kleinberg and É. Tardos. Algorithm Design. Pearson Education,
2006.
[16] C. Komusiewicz, F. Hüffner, H. Moser, and R. Niedermeier. Isolation
concepts for efficiently enumerating dense subgraphs. Theoretical Computer Science, 410(38):3640–3654, 2009.
[17] M. Lahiri and T. Y. Berger-Wolf. Periodic subgraph mining in dynamic
networks. Knowledge and Information Systems, 24(3):467–497, 2010.
[18] J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, pages 177–187. ACM, 2005.
[19] O. Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12(4):239–280, 2016.
[20] O. Michail and P. G. Spirakis. Traveling salesman problems in temporal
graphs. Theoretical Computer Science, 634:1–23, 2016.
31

[21] K. A. Naudé. Refined pivot selection for maximal clique enumeration
in graphs. Theoretical Computer Science, 613:28–37, 2016.
[22] V. Nicosia, J. Tang, C. Mascolo, M. Musolesi, G. Russo, and V. Latora.
Graph metrics for temporal networks. In P. Holme and J. Saramäki,
editors, Temporal Networks, pages 15–40. Springer Berlin Heidelberg,
2013.
[23] T. Opsahl and P. Panzarasa. Clustering in weighted networks. Social
Networks, 31(2):155–163, 2009.
[24] J. Stehlé, N. Voirin, A. Barrat, C. Cattuto, L. Isella, J.-F. Pinton,
M. Quaggiotto, W. Van den Broeck, C. Régis, B. Lina, et al. Highresolution measurements of face-to-face contact patterns in a primary
school. PLoS ONE, 6(8):e23176, 2011.
[25] E. Tomita, A. Tanaka, and H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments.
Theoretical Computer Science, 363(1):28–42, 2006.
[26] T. Uno and Y. Uno. Mining preserving structures in a graph sequence.
Theoretical Computer Science, 654:155–163, 2016.
[27] P. Vanhems, A. Barrat, C. Cattuto, J.-F. Pinton, N. Khanafer, C. Régis,
B.-a. Kim, B. Comte, and N. Voirin. Estimating potential infection
transmission routes in hospital wards using wearable proximity sensors.
PLoS ONE, 8(9):e73970, 2013.
[28] J. Viard, M. Latapy, and C. Magnien. Revealing contact patterns
among high-school students using maximal cliques in link streams.
In Proceedings of the 2015 IEEE/ACM International Conference on
Advances in Social Networks Analysis and Mining, pages 1517–1522.
ACM, 2015.
[29] T. Viard, M. Latapy, and C. Magnien. Computing maximal cliques in
link streams. Theoretical Computer Science, 609:245–252, 2016.

32

