# Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size

Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita, Davide

Rucci, Takeaki Uno, Kunihiro Wasa

► To cite this version:

Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita, Davide Rucci, et al. Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size. Algorithmica, 2025, 87 (9), pp.1247-1273. 10.1007/s00453-025-01312-0. hal-05435077

HAL Id: hal-05435077

https://inria.hal.science/hal-05435077v1

Submitted on 30 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size

Alessio Conte⁵ · Roberto Grossi⁵ · Yasuaki Kobayashi¹ · Kazuhiro Kurita³ · Davide Rucci⁶ · Takeaki Uno⁴ · Kunihiro Wasa²

Received: 25 March 2024 / Accepted: 9 April 2025 / Published online: 13 May 2025

© The Author(s) 2025

## Abstract

Graphlets of order *k* in a graph *G* are connected subgraphs induced by *k* nodes (called *k*-graphlets) or by *k* edges (called edge *k*-graphlets). They are among the interesting subgraphs in network analysis to get insights on both the local and global structure of a network. While several algorithms exist for discovering and enumerating graphlets, the amortized time complexity of such algorithms typically depends on the size of the graph *G*, or its maximum degree. In real networks, even the latter can be in the order of millions, whereas *k* is typically required to be a small value. In this paper we provide the first algorithm to list all graphlets of order *k* in a graph *G* = (*V*, *E*) with an amortized time complexity depending solely on the order *k*, contrarily to previous approaches where the cost depends *also* on the size of *G* or its maximum degree. Specifically, we show that it is possible to list *k*-graphlets in *O*(*k*²) time per solution, and to list edge *k*-graphlets in *O*(*k*) time per solution. Furthermore we show that, if the input graph has bounded degree, then the amortized time for listing *k*-graphlets is reduced to *O*(*k*). Whenever *k* = *O*(1), as it is often the case in practical settings, these algorithms are the first to achieve constant time per solution.

**Keywords** Enumeration · Graph algorithms · Amortization · Graphlets · Subgraphs

## 1 Introduction

Subgraphs are a well-known example of *patterns* or *motifs* that can be extracted from
graphs to discover meaningful insights on both the local and global structure of the
network they represent. In recent years there has been growing attention on the graph
motif problem [1–3] which asks to list or count a specific kind of pattern (formalized as
subgraphs) in a complex network. These subgraphs not only offer valuable information
on the underlying network’s properties, they also serve as building blocks in many
fields such as biology and bioinformatics, sociology, computer networks, and transport
engineering: in fact, in these kinds of networks, subgraphs are able to capture and
highlight the community structure of the network itself [4], a concept that is ever so

<footnote>Extended author information available on the last page of the article</footnote>
<figure><img src="image_2.png" /><figcaption>**Fig. 1** a A graph $G = (V, E)$ with $|V| = 4$ vertices and $|E| = 5$ edges. b All 3-graphlets contained in G. c All edge 3-subgraphs, i.e., edge 3-graphlets in G, where dotted edges denote subgraphs that are also acyclic (3-subtrees). Note that some of the k-graphlets are also edge k-graphlets, but this is not necessarily so; also, some edge k-graphlets have a number of vertices different from k</figcaption></figure>

important when people or any other entities are tightly interconnected. In this paper, we study two possible specializations of the main subgraph definition for a given integer, called order k: vertex-induced k-subgraphs (known as k-graphlets [5]) and edge-induced k-subgraphs, as illustrated in Fig. 1. Namely, a k-graphlet is a connected subgraph induced by k vertices. In this paper, to be consistent with k-graphlets, we refer to a connected edge-induced subgraph with k edges as edge k-graphlet.

We observe that k-graphlets are getting momentum for their numerous fields of application, such as large graph comparison [6, 7] again by kernelization, understanding the role of genes in pathways and cancer mechanisms [8], and finding important nodes in a network [9]. Special cases of k-graphlets, such as triangles when k = 3, or cliques, have been investigated for community detection purposes, as they help speeding up the process of identifying (possibly larger) communities in graphs [10–13]. Also, edge k-graphlets find their usage in wildly different domains [14], such as graph databases where they are used for indexing purposes [15], kernelization in machine learning models [16], and planar graphs [17], to name a few.

We now state the problems that will be considered in this paper.

**Problem 1** (k-Graphlet Enumeration) Given an undirected graph $G = (V, E)$, list all the connected subgraphs of $G$ induced by a subset $C \subseteq V$ of k vertices (see Fig. 1b).

**Problem 2** (Edge k-Graphlet Enumeration) Given an undirected graph $G = (V, E)$, list all the connected subgraphs of $G$ induced by a subset $S \subseteq E$ of k edges (see Fig. 1c).

As these problems have an exponential amount of solutions, the input time complexity of any algorithm solving these problems is exponential in the worst case; however, when tackling enumeration tasks it is common practice to give an output-sensitive analysis instead, where the time complexity is a function of the output size. Specifically, let
$N$ be the total number of solutions found. If the overall cost is $O(\text{poly}(|V|) + N \cdot f(k))$ time for some function $f$, we say that the amortized cost per solution, i.e., the amortized time complexity is $O(f(k))$.<fnref n="1" /> It is output-sensitive as this cost grows linearly with $N$, the number of solutions.

Our main result is to provide new enumeration algorithms requiring $O(k^2)$ amortized time per $k$-graphlet in Problem 1, and $O(k)$ amortized time per edge $k$-graphlet in Problem 2. When compared to the state of the art discussed in Sect. 1.1, (i) we provide a faster amortized cost, and (ii) we obtain the first parameterized cost per solution that has no dependency on the graph size $|V|$ or $|E|$, or its maximum degree $\Delta$: typically, order $k$ is a small value whereas $|V|$, $|E|$, and $\Delta$ can be very large, so our algorithms scale well as their amortized time complexity depends on $k$ alone. Based on our results, it is also possible to derive delay bounds, i.e., to bound the time that interleaves between the output of two consecutive solutions. For instance, using simple arguments, we obtain a $O(k^3 + k\Delta)$ delay for the $k$-graphlet enumeration task, but we also how that with more refined techniques we can achieve a $O(k^2)$ delay.

On the technical side, our contribution is the following. We note that enumeration algorithms based on the so-called binary partition approach often exhibit simplicity in both correctness and algorithmic behavior: binary partition involves determining how to expand each partial solution by either including an additional element $e$ or explicitly excluding $e$. For instance, algorithms for enumerating paths, cycles, spanning trees, induced matchings, induced subtrees, induced subgraphs with a girth constraint, dominating sets, induced bipartite graphs, and $k$-degenerate induced subgraphs, all make use of binary partition (the reader can refer to [18]). However, performing a refined analysis of these algorithms presents a significant challenge. In our proposed algorithms for Problem 2, we leverage the *push-out amortization* technique introduced in [19]. The crux of this analysis lies in speeding up the lower part of the enumeration tree, where algorithms based on binary partition generate recursive calls, forming a tree structure. In many instances, a recursive call within the lower part of this tree structure deals with an input graph featuring a substantial number of vertices/edges either considered or forbidden for use. In such cases, the possibility arises to eliminate these specified vertices/edges, thereby reducing the size of the input graph. This operation, in turn, accelerates the computation time of the lower part of the enumeration tree. As the size of an enumeration tree is definitively influenced by the size of its lower section, where the number of descendants increases exponentially, hastening the lower part of an enumeration tree results in exponential improvements in overall efficiency. A similar idea is called *kernelization* [20, 21] in the field of parameterized algorithms, reducing the size of the input graph.

## 1.1 Related Work

For $k$-graphlets [5], there are numerous studies on techniques for enumerating all of them, those with exactly $k$ vertices and those with at most $k$ vertices,<fnref n="2" /> each of these

<footnote n="1">¹ $O(\text{poly}(|V|))$ does not contribute to the amortized time since it is independent of $N$.</footnote>

<footnote n="2">² It is also possible to enumerate all vertex-induced connected subgraphs, regardless of the value of $k$: for this task there already exists a constant amortized time algorithm [19].</footnote>
variants being suitable for different kinds of applications. Historically, one of the first algorithms able to enumerate all *k*-graphlets in a generic graph is called ESU [22, 23], and works with a classical binary partition approach. Other tools for this task include Escape [24], FaSE [25], Kavosh [26], and Jesse [27] among others, for which we refer the reader to the survey in [28]. An interesting case is the PGD algorithm [29], which is able to compute the exact number of *k*-graphlets without having to explicitly enumerate all of them, by some clever combinatorial arguments. However, due to the nature of its combinatorial reasoning, PGD is limited to values of *k* ≤ 4, because even for *k* = 5 the cases to be considered are too many to have both a reasonable running time and a small number of theoretical arguments to be exploited.

A recent work by Komusuewicz and Sommer [30], later improved in practice by Conte et al. [31], sets the state of the art to $O(k^2\Delta)$ delay time per $k$-graphlet, where $\Delta$ is the maximum degree of the input graph $G$, and the delay is the worst case time to output the next solution, and cannot be smaller than the amortized time. For the relaxed case of graphlets with at most $k$ vertices, the delay becomes $O(k + \Delta)$ time. Wang et al. [32] have recently proposed three algorithms with delay, respectively, of $O(k \cdot \min\{|V| - k, k\Delta\}(k \log \Delta + \log|V|))$, $O(k \cdot \min\{|V| - k, k\Delta\} \cdot |V|)$, and $O(k^2 \cdot \min\{|V| - k, k\Delta\} \cdot \min\{k, \Delta\})$: these bounds can be lower than the state of the art $O(k^2\Delta)$ of [30], under some specific assumptions on the value of $k$.

Compared to the state of the art, our algorithms presented in this paper belong to the class of enumeration algorithms “for a given $k$”, with no limitations on the value of $k$. Our algorithms improve the current state of the art from roughly $O(k^2\Delta)$ amortized time to $O(k^2)$ per $k$-graphlet or $O(k)$ per edge $k$-graphlet, thus eliminating a troublesome theoretical dependency on $\Delta$. For the sake of completeness, there also exist non-combinatorial algorithms that estimate $k$-graphlet counts in a graph using deep learning techniques [33], but it is difficult to analyze their amortized time complexity.

# 2 Preliminaries

In this section we give the necessary notation and terminology about graphs. In addition, we give an overview of a technique called *binary partition* to design efficient enumeration algorithms. In Sect. 2.2, we also show a technique for analyzing the amortized time complexity of enumeration algorithms called *push-out amortization* [19].

## 2.1 Notation

Let $G = (V, E)$ be an undirected graph. Unless stated otherwise, graphs have no self-loops or parallel edges. We may use notations such as $E(G)$ or $V(G)$ to refer to a set of edges or vertices, respectively, for a given graph instance $G$. We also use shorthands for $|V|$ and $|E|$ such as $n$ and $m$, respectively. For an edge $e = \{u, v\}$, we call $u$ and $v$ *endpoints of* $e$. For a vertex $v$, an edge $e$ is an *incident edge of* $v$ if $v$ is an endpoint of $e$. We denote the set of incident edges of $v$ in $G$ as $\Gamma_G(v)$. The value $|\Gamma_G(v)|$ is called the *degree of* $v$ and denote it as $d_G(v)$. Moreover, $\max_{v \in V} d_G(v)$ is the *maximum*

<figure><img src="image_3.png" /></figure>
degree of G and denote it as $\Delta$. We drop the subscript when it can be deduced to from the context. A vertex $v$ is a *neighbor of* $u$ if $E$ has an edge $\{u, v\}$. The set of neighbors of $v$ is the *open neighborhood of* $v$ and denote it $N(v)$, and we define the open neighborhood of a set of vertices $U$ as $\bigcup_{u \in U} N(u) \setminus U$. Similarly, we define the closed neighborhood of $v$ and $U$ as $N[v] := N(v) \cup \{v\}$ and $N[U] := \bigcup_{u \in U} N(u) \cup U$. This reasoning can be extended also to a set of edges $I$: in particular, given $I \subseteq E$, we define $\Gamma(I)$ as the set of edges incident to at least one of the endpoints of an edge $e \in I$, i.e. $\Gamma(I) = \{e = (u, v) \in E \mid \exists e' = (u', v') \in I : u = u' \vee u = v' \vee v = u' \vee v = v'\}$.

A vertex sequence $P:=(v_1, \dots, v_\ell)$ is a *path* if for any $1 \le i < \ell$, $G$ has an edge $\{v_i, v_{i+1}\}$ and $v_i$ and $v_j$ are distinct for any $1 \le i < j \le \ell$. Vertices $v_1$ and $v_\ell$ are *endpoints of* $P$ and $P$ is also called a $v_1-v_\ell$ path. The *length* of path $P$ is the length of the sequence minus one, i.e., the number of edges traversed. The *distance* between vertices $u$ and $v$ is the length of a shortest $u-v$ path. A graph $G$ is *connected* if, for any pair of vertices $u$ and $v$, $G$ has a $u-v$ path. Moreover, we define *dist*($X$, $e$), the distance of an edge $e = (u, v)$ from a set of vertices $X$, as the length of a shortest path from either $u$ or $v$, depending on which one is closer, to the closest vertex belonging to $X$. In this paper we assume that the graph $G$ is connected. If $G$ is not connected, it suffices to consider each connected component of $G$ separately. A sequence $C:=(v_1, \dots, v_\ell, v_1)$ is a *cycle* if the sequence $(v_1, \dots, v_\ell)$ is a path and $G$ has an edge $\{v_1, v_\ell\}$. For $G$ and a subset of vertices $U \subseteq V$, a graph $H = (U, F)$ is called a *vertex-induced subgraph* if $F:=\{\{u, v\} \in E \mid u, v \in V\}$. Similarly, for $G$ and a subset of edges $F \subseteq E$, a graph $H = (U, F)$ is called an *edge-induced subgraph* or simple *subgraph* if $U:=\bigcup_{e \in F} e$. We denote a vertex- or edge-induced subgraph induced by $X$ as $G[X]$. Moreover, we denote a vertex- or edge-induced subgraph induced by $V \setminus X$ or $E \setminus X$ as $G - X$. For a vertex $v$ (an edge $e$), we denote $G - \{v\}$ ($G - \{e\}$) as $G - v$ ($G - e$). We also define the *contraction* of an edge $e = \{u, v\}$ as the process of removing one of its extremes, e.g., $v$, and inserting a new edge from $u$ to all the vertices in $\Gamma(v)$; we remark that contraction can sometimes create multi-edges.

We recall that in this paper, we call a connected vertex- or edge-induced subgraph with exactly $k$ vertices or edges a *k-graphlet* or an *edge k-graphlet*. An edge subtree $T$ is a *subtree* of $G$ if $T$ has no cycles. If $T$ has exactly $k$ edges, we call $T$ a *k-subtree* (see Fig. 1 for a visualization of these three concepts).

## 2.2 Basic Techniques for Efficient Enumeration

Let us introduce in this section the main algorithmic techniques used in the paper.

**Binary Partition** (also *branching* or *flashlight* approach), is a basic technique that recursively splits the space of solutions $S$ into two sets $S'$ and $S''$ such that $S = S' \cup S''$. Consider for example the enumeration of all $k$-graphlets in a graph $G = (V, E)$. We first pick a vertex $v \in V$ and partition $S$, the space of all $k$-graphlets of $G$, into two sets: one containing all solutions that include $v$, the other containing all solutions that do not include $v$. If the aforementioned sets contain more than one solution, we recursively proceed until we can print a unique $k$-graphlet. This process defines an implicit tree structure $T = (\mathcal{V}, \mathcal{E})$ that we call the *enumeration tree* or *recursion tree*. We will refer to a $X \in \mathcal{V}$ as a tree *node* or an *iteration*, and we call a node $Y \in \mathcal{V}$ a *child* of $X$
if and only if there exists an arc (X, Y) ∈ E. The set of all children of X is called ch(X). The parent–child relation of T can be defined as follows. Let X be a node of T, corresponding to an instance of the problem on the graph G<sub>X</sub> = (V<sub>X</sub>, E<sub>X</sub>). The children nodes of X either consider v ∈ V as part of the solution, or remove it from the graph. Thus, the left child X<sub>l</sub> of X obtains the same input graph G<sub>X</sub>, but includes v in all subsequent solutions (e.g. by keeping it in a special set S), while the right child obtains the input graph G<sub>X<sub>r</sub></sub> = (V<sub>X</sub> \ {v}, {(u, w) ∈ E<sub>X</sub> | u, w ∈ V<sub>X</sub> \ {v}}). A key factor when designing an efficient enumeration algorithm based on this technique, is to ensure that each internal node in T has at least two children. Suppose that any internal node X ∈ T can generate all its children in T(X) time, and that each leaf node produces exactly one solution. When every internal node has exactly two children, the number of solutions, i.e. of leaves, linearly bounds the number of internal nodes, allowing us to conclude that the amortized time complexity of this enumeration algorithm is O(max<sub>X∈T</sub> T(X)). Notice that if there exists an internal node with exactly one child in T, the amortized time complexity of the algorithm worsens to O(d·max<sub>X∈T</sub> T(X)), where d is the depth of T.

This technique has been widely used in the literature for the enumeration of struc-
tures like s–t paths, cycles, minimal s–t cuts, spanning trees, induced matchings,
induced bipartite subgraphs, induced k-degenerate subgraphs, independent sets, and
more [34–40]. In this paper, we will use this strategy for designing the algorithm of
Sect. 3.

We now introduce another technique that can be used for the time complexity
analysis of binary partition algorithms called *push-out amortization* [19]. The idea
of this kind of analysis is to speed up the computation of the nodes in the bottom
level of the enumeration tree. In fact, as each internal node has at least two children,
the number of nodes in the bottom part is exponentially larger than that of nodes
in top part. Therefore, by speeding up the lowest nodes, we expect to exponentially
improve the time complexity of the whole algorithm. With this idea in mind, one
has to design an algorithm respecting the following conditions: (1) the overall time
complexity is dominated by the complexity of leaf nodes, and (2) leaves have “small”
time complexity. For reference, the independent set enumeration problem can also be
solved efficiently by push-out amortization, as well as other enumeration problems
[19, 40].

In order to prove that the total time of the bottom levels of an enumeration tree
dominate the total running time of an algorithm, it is important to ensure that the total
time of children nodes is somewhat larger than that of the parent node. However, at
the same time we must also ensure that the running time of leaf nodes is kept small,
and satisfying both of these conditions is not always easy. This is because usually
when designing an algorithm in a way that the time complexity of a child node is
large, it is difficult to ensure condition (2). On the other hand, when we design the
leaves with a small time complexity, it becomes difficult to ensure condition (1). Uno
[19] established a sufficient condition to solve the above situation called the *push-out
(PO) condition*.

<figure><img src="image_4.png" /></figure>
**Theorem 1** (The PO condition [19]) If, for every internal node X of $\mathcal{T}$, it holds that

$$ \bar{T}(X) = \sum_{Y \in ch(X)} T(Y) \geq \alpha T(X) - \beta(|ch(X)| + 1)T^*, $$

where $\alpha > 1$ and $\beta \geq 0$ are constants and $T^*$ is the worst case running time of processing any leaf node of $\mathcal{T}$, then, the amortized time of each node X in $\mathcal{T}$ is $O(T^*)$.

Suppose, for example, that for every leaf node of $\mathcal{T}$, the algorithm outputs a distinct solution (we assume, for the sake of convenience, that one solution corresponds to exactly one leaf and vice versa). If every internal node of $\mathcal{T}$ has at least two children and $T^*$ is upper bounded by a constant, then the algorithm runs in amortized constant time per solution. The algorithm presented in Sect. 4 is designed according to the push-out amortization strategy.

Finally, a note on data structures is in order: we are describing recursive algorithms that make changes to a graph as they proceed. Since creating copies of the graph for children recursive calls would dominate the complexity, we keep a single dynamic copy of the graph and edit it as necessary, undoing the changes as we backtrack.

We assume using a graph data structure that allows the key operation of

* Iterating over the neighbors of a node $v$ in $O(d_G(v))$ time.

* Deleting or inserting an edge in $O(1)$ time.

* Deleting or inserting a vertex $v$ in $O(d_G(v))$ time.

* Contracting an edge $e = \{u, v\}$ in either $O(d_G(u))$ or $O(d_G(v))$ time.

In particular observe how the first two items are the essential ones, as we can delete a vertex $v$ in $O(d_G(v))$ time by deleting its incident edges one by one, and we can contract $e = \{u, v\}$ in $O(d_G(u))$ time by removing every edge $\{u, x\}$ incident to $u$ and replacing it with the edge $\{v, x\}$. This type of structure is typically considered folklore knowledge, but more details on how to maintain it can be found, e.g., in [41].

## 2.3 Obtaining Delay Bounds

As pointed out earlier, it is possible to transform these amortized time bounds into delay. Let us briefly observe how. In particular, we can use the *Output Queue Method* [42]. It consists in creating a bounded queue $Q$ of length $\lceil 2T^*/\bar{T} \rceil + 1$, where $T^*$ is the maximum delay, i.e. the cost of all the ancestors of a leaf iteration in the recursion algorithm that outputs a solution, and $\bar{T}$ the average time between two outputs (i.e. the amortized cost). During the execution of our algorithm, instead of outputting a solution directly, we place the solution into the end of $Q$. If $Q$ is full, then we pop the front and output that solution. If we reach the end of the algorithm and $Q$ is not empty, output all the remaining solutions. By using this technique we can regularize the delay and make sure to output a solution every $\bar{T}$ time. In particular, we can obtain $O(k^2)$ and $O(k)$ delay respectively for $k$-graphlet enumeration and edge $k$-graphlet enumeration. We can then proceed to give amortized bounds on our algorithms, knowing that they can always be translated into delays with the Output Queue Method. For more details
on this technique, we refer the reader to [42]. In what follows, we will not explicitly adopt this technique in the pseudocode in order not to further complicate the analysis of our algorithms, but we note that the regularized delay is achievable through small modifications to each algorithm.

# 3 Enumeration of k-Graphlets

In this section we describe an algorithm for efficient k-graphlet enumeration in amortized $O(k^2)$-time, based on binary partition. We start by discussing an algorithm for the enumeration of k-graphlets containing a given vertex $r$, then we expand the strategy to obtain all the k-graphlets of $G$.

## 3.1 Enumeration of All k-Graphlets with a Specific Vertex

Let $r \in V$ be an arbitrary vertex of $G = (V, E)$, $In$ and $Ex$ be two disjoint vertex sets, and $S(G, In, Ex, k)$ be the set of all k-graphlets of $G$ that contain all and only the vertices in the set $In$, and do not contain any vertex in $Ex$. For brevity, when $G$ is clear from the context, we denote this set as $S(In, Ex, k)$. Since we are interested in k-graphlets containing the specified vertex $r$, in the rest of this section we always assume that $r \in In$. The basic strategy consists of partitioning the set $S(In, Ex, k)$ into two sets $S(In \cup \{v\}, Ex, k)$ and $S(In, Ex \cup \{v\}, k)$, given a vertex $v \in N(In) \setminus Ex$. Then, we check if these sets contain at least one solution by choosing an arbitrary vertex from $In$, running a graph traversal from it, excluding vertices in $Ex$, and checking if we reach $k - |In|$ vertices to be added to $In$. This strategy ensures that $G[In]$ is connected, as it is connected at first (initially $In = \{r\}$) and we add neighbors of $In$ at each step.

Therefore, in what follows, we assume that $G[In]$ is connected, and we also omit the set $Ex$ from the notation using this simplifying observation.

**Observation 1** $S(G, In, Ex, k) = S(C_{In}, In, \emptyset, k)$, where $C_{In}$ is the connected component in $G - Ex$ that contains all the vertices in $In$.

In what follows, unless otherwise specified, we assume that the graph is stored using adjacency lists, providing $O(d(v))$-time deletion/restore of any vertex $v \in V$. In the algorithms we represent a graphlet implicitly, by keeping the set of its vertices. Any induced subgraph $G[S]$ is not explicitly represented, and we can traverse it by starting from a vertex in the corresponding set $S$.

### 3.1.1 Amortized Linear-Time Enumeration

First, we give an amortized $O(m)$-time enumeration algorithm that will be used as a subroutine in the subsequent $O(k^2)$ amortized time algorithm.

It can be easily shown that the simple binary partition algorithm discussed in Sect. 3.1 runs in amortized $O(nm)$ time, since each recursive call takes $O(m)$ time and the depth of $T$ is at most $n$. In this approach, the number of tree nodes in $T$ is $O(nN)$, where $N$ is the number of leaves, that is, the number of k-graphlets. Therefore, the

<figure><img src="image_5.png" /></figure>
<caption>**Algorithm 1:** An amortized *O*(m)-time algorithm for *k*-graphlet enumeration</caption>

**Input:** A graph *G*, a set of vertices *In*, an integer *k*
**Output:** All *k*-graphlets that contain *In* in *G*
1 **Function** LIN-ENUM-V(*G*, *In*, *k*)
2     **if** |*In*| = *k* **then** output *In* and return
3     **while** N(*In*) has a mandatory vertex *u* do
4         *In* ← *In* ∪ {*u*}
5         **if** |*In*| = *k* **then** Output *In* and return
6     Let *v* be a vertex in *N*(*In*)
7     LIN-ENUM-V(*G*, *In* ∪ {v}, ∅, *k*)
8     LIN-ENUM-V(*G* − *v*, *In*, *k*)
    // *v* is non-mandatory

amortized time complexity is *O*(nm). To improve this time complexity, we first reduce the number of nodes *T* without worsening the time complexity of each node and, in particular, we ensure that each node produces exactly two children. To this end, we detect a vertex *v* such that *S*(In, Ex ∪ {v}, *k*) has no solution.

A vertex *v* is *mandatory* for *G*, *In* and *k* if the connected component in *G* − *v* that contains the vertices in *In* has at most *k* − 1 vertices. Notice that a vertex *v* is *mandatory* if and only if *S*(G, *In*, *k*) = *S*(G, *In* ∪ {v}, *k*). In addition, a *mandatory* vertex is an *articulation point* if the connected component in *G* that contains *In* has at least *k* + 1 vertices.

In our partitioning strategy, the basic operation is to determine if $\mathcal{S}(G, In, k)$ is non-empty, and if a vertex $v$ is mandatory or not. We show that both operations can be done in $O(\min\{m, k^2, k\Delta\})$ time.

**Lemma 2** Let *G* be a graph, *k* be an integer, and *In* ≠ ∅ a set of vertices such that *G*[*In*] is connected. We can determine if *S*(*G*, *In*, *k*) is empty or not in *O*(min{*m*, *k*<sup>2</sup>, *k*Δ}) time. Moreover, for a vertex *v*, we can check whether *v* is mandatory or not with the same time complexity.

**Proof** We show that it can be done with a standard graph search technique, the breadth-first search. If the connected component in *G* that contains *In* has at least *k* vertices, *S*(*G*, *In*, *k*) is non-empty, and this can be checked in *O*(m) time. To improve this time complexity, we terminate the breadth-first search as soon as we find *k* vertices. Let *U* and *F* be two sets of vertices and edges respectively, explored by the breadth-first search. Since the breadth-first search terminates when we find *k* vertices, each edge *e* ∈ *F* connects vertices in *U*. Therefore, |*F*| is bounded by min{*k*<sup>2</sup>, *k*Δ} and the breadth-first search terminates in *O*(min {*m*, *k*<sup>2</sup>, *k*Δ}) time. Moreover, even if we ignore *v*, the number of edges in *F* increases at most by *k*, thus we can check whether *v* is mandatory or not with the same time complexity. □

We are now ready to describe a linear amortized time algorithm for *k*-graphlet enumeration, whose pseudocode is shown in Algorithm 1. We first prove its correctness, then we discuss its computational complexity.

**Theorem 2** *Algorithm 1 enumerates all *k*-graphlets in *G* that contain *In* ≠ ∅.*
**Proof** Let $X$ be a node in $\mathcal{T}$, $G_X$ be the input graph of the call $X$, $In_X$ be a set of vertices such that $G_X[In_X]$ is connected. We show that each node in $\mathcal{T}$ partitions $S(G_X, In_X, k)$ into two non-empty sets $S(G_X, In_X \cup \{v\}, k)$ and $S(G_X - v, In_X, k)$. By definition, adding mandatory vertices in $In_X$ does not change the set of $k$-graphlets. Moreover, since we add mandatory vertices that are adjacent to a vertex in $In_X$, we do not break the connectivity of $G_X[In_X]$. Let $S$ be a $k$-graphlet in $S(G_X, In_X, k)$: if $S$ contains $v$, $S \in S(G_X, In_X \cup \{v\}, k)$, otherwise $S \in S(G_X - v, In_X, k)$. From the definition of $S(G_X, In_X, k)$, $S(G_X, In_X \cup \{v\}, k)$ and $S(G_X - v, In_X, k)$ are disjoint. Therefore, in each node $X$ of $\mathcal{T}$, we can partition the set of $k$-graphlets and Algorithm 1 output all $k$-graphlets containing $In$.
□

Next, we analyze the time complexity of Algorithm 1.

**Theorem 3** *Algorithm 1 runs in $O(n + N \cdot (m + 1))$ time and $O(n + m)$ space, where $N$ is the number of $k$-graphlets in $G$.*

**Proof** We first consider the time complexity of each node $X$, i.e., of a single recursive call. First, we enumerate all articulation points in $O(n+m)$ time using Tarjan's articulation point enumeration algorithm [43, 44]. Using the block-cut tree obtained from Tarjan's algorithm, we can obtain all mandatory vertices in $O(n+m)$ time; thus, the while loop on line 3 takes $O(n+m)$ time. Since the other operations can be done trivially in $O(n+m)$ time, the time complexity of $X$ is $O(n+m)$. Now we consider the total time complexity of Algorithm 1 by analyzing the relation between the number of solutions and the number of nodes of $\mathcal{T}$. Since each leaf of $\mathcal{T}$ outputs one solution and each internal node of $\mathcal{T}$ has at least two children, the number of leaves of $\mathcal{T}$ is bounded by $O(N)$. Therefore, the total time complexity of this algorithm is $O(n + N(m+1))$. Regarding the space complexity, in each node $X$ of $\mathcal{T}$, we store only the difference of $In_X$ and $G_X$, achieving a total space complexity of $O(n+m)$. □

### 3.1.2 Amortized $O(k^2)$-Time Enumeration

We can now introduce our amortized $O(k^2)$-time $k$-graphlet enumeration algorithm. The basic strategy of this algorithm is the same as Algorithm 1, fine-tuned in order to achieve amortized $O(k^2)$-time. The enumeration of mandatory vertices demands $O(m)$ time if done in a naive way, using a block-cut tree and a linear-time articulation point enumeration algorithm [44]: this may become the bottleneck of the enumeration process. To overcome this difficulty, we use Lemma 2. Using this Lemma, we can efficiently determine whether a vertex $v$ is mandatory or not. If we can find a non-mandatory vertex, then we can generate two children instances in the corresponding recursion tree $\mathcal{T}$. We now show that $N(In)$ has at most one mandatory vertex when $G$ is sufficiently large.

**Lemma 3** Let $U \neq \emptyset$ be a set of vertices of a graph $G$ such that $G[U]$ is connected, $|U| \le k-2$, and $G$ has at least $k$ vertices. Let $x$ and $y$ be distinct vertices in $N(U)$. If $x$ and $y$ are both mandatory for $G$, $U$, $k$, then $n < 2k$.

**Proof** Since $x$ and $y$ are mandatory, both $x$ and $y$ must be articulation points in $G$, and they are in the connected component of the graph containing $U$ (because they

<figure><img src="image_6.png" /></figure>
<caption>**Algorithm 2:** An amortized *O*(k²)-time k-graphlet enumeration algorithm.</caption>

**Input:** A graph *G*, an integer *k*, a connected set of vertices *In*
**Output:** All *k*-graphlets of *G* that contain *In*
1 **Function** ENUM-V(*G*,*In*,*k*)
2 &nbsp;&nbsp;&nbsp;**if** |*In*| = *k* − 1 **then**
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** *u* ∈ *N*(*In*) **do** output *In* ∪ {*u*}
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return**
5 &nbsp;&nbsp;&nbsp;**while** |*N*(*In*)| = 1 **do**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Let *v* be the vertex in *N*(*In*)
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*In* ← *In* ∪ {*v*}
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** |*In*| = *k* − 1 **then**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** *u* ∈ *N*(*In*) **do** output *In* ∪ {*u*}
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return**
11 Let *x*, *y* be two distinct vertices in *N*(*In*)
12 **if** either *x* or *y* is non-mandatory for *G*, *In*, *k* **then**
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Let *z* be a non-mandatory vertex in {*x*, *y*}
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ENUM-V(*G*, *In* ∪ {*z*}, *k*)
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ENUM-V(*G* − *z*, *In*, *k*)
16 **else**
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LIN-ENUM-V(*G*, *In*, *k*)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**//** |*V*| < 2*k* by Lemma 3
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**//** |*V*| < 2*k* by Lemma 3

are neighbors of vertices of *U*). Let *T*<sub>*C*</sub> be a biconnected-component tree of *G*: this component must contain at least *k* + 1 vertices, otherwise it would not contain any solution and we would skip it (see Algorithm 3). We denote the connected component in *G* − *x* that contains the vertices in *U* as *T*<sub>*C*</sub>(*x*, *U*, 1) and the other connected components in *G* − *x* as *T*<sub>*C*</sub>(*x*, *U*, 0). Notice that *x* ∈ *T*<sub>*C*</sub>(*y*, *U*, 1) and *y* ∈ *T*<sub>*c*</sub>(*x*, *U*, 1) by construction. Since both *x* and *y* are mandatory, both *T*<sub>*C*</sub>(*x*, *U*, 1) and *T*<sub>*C*</sub>(*y*, *U*, 1) have at most *k* − 1 vertices. Moreover, any vertex in *G* is contained either in *T*<sub>*C*</sub>(*x*, *U*, 1) or *T*<sub>*C*</sub>(*y*, *U*, 1), because *x* and *y* are both mandatory. As any shortest path from *x* to *y* can only go through vertices of *U*, because of the size of *G*, we obtain that the corresponding *T*<sub>*C*</sub>(*x*, *U*, 1) and *T*<sub>*C*</sub>(*y*, *U*, 1) are disjoint, otherwise *x* and *y* would not be mandatory. Therefore, the number of vertices of *G* in this case is at most |*V*(*T*<sub>*C*</sub>(*x*, *U*, 1)| + |*V*(*T*<sub>*C*</sub>(*y*, *U*, 1)| ≤ 2*k* − 2. □

We can now prove the amortized time complexity of Algorithm 2. We omit the proof of correctness for Algorithm 2 as it follows the same arguments used in Theorem 2, and from the binary partition structure of the algorithm (see also [30]).

**Theorem 4** ENUM-V(*G*, *In* = {*v*ᵢ},*k*) (*Algorithm 2* runs in *O*(*N*ᵢ · *k*²) time and *O*(*n* + *m*) space, where *N*ᵢ is the number of *k*-graphlets that contain *In* = {*v*ᵢ}.

**Proof** We analyze the time complexity of each tree node *X* ∈ *T*, and we denote by *G*<sub>*X*</sub> the input graph of the call *X*, with the corresponding set *In*<sub>*X*</sub>. Notice that *k* is the same for all instances in *T*, and that *X* is not a leaf node of the recursion tree. We first analyze the time complexity when |*In*<sub>*X*</sub>| = *k* − 1 (there cannot be a node satisfying
$|In_X| = k$ as the base case of the algorithm is for $|In_X| = k - 1$).<fnref n="3" /> In this case, we can enumerate all $k$-graphlets in $O(k^2 + k \cdot N_X)$ time, where $N_X = |S(G_X, In_X, k)|$, and the node $X$ produces only leaf children. For each $u \in N_{G_X}(In)$, $In \cup \{u\}$ is a $k$-graphlet. Therefore, $\sum_{v \in S} d_{G_X}(v)$ is upper-bounded by $k^2 + k \cdot N_X$.

Now consider the case $|In_X| < k - 1$. When $N_{G_X}(In_X)$ has only one vertex, we can find it in $O(k^2)$ time by looking at the neighbors of the set and stopping as soon as we find one not in the set, and it is easy to compute all such vertices in the same time complexity within the loop of line 5 of Algorithm 2. Thus, in what follows we assume that $N_{G_X}(In_X)$ contains at least two vertices, and that the tree node $X$ produces non-leaf children. Let $x$ and $y$ be two distinct vertices in $N_{G_X}(In_X)$: using Lemma 2, we can check if $x$ and $y$ are mandatory in $O(k^2)$ time. If both $x$ and $y$ are mandatory, the time complexity of $X$ is $O(k^2)$ since the number of vertices in $G_X$ is $O(k)$.

Suppose now that one of $x$ or $y$ is non-mandatory and call $z$ such vertex. To compute $G_X - z$, we need $O(d_{G_X}(z))$ time using standard data structures. Therefore, if $d_{G_X}(z) < 3k$, the time complexity of $X$ is $O(k^2)$. In the case that $d_{G_X}(z) \ge 3k$, we consider the following amortized analysis: let $Y$ be a node generated by $G_X$ and $In_X \cup \{z\}$. We call left child a child of a recursive node generated by adding one vertex to $In$ (i.e., in line 14), whereas we call right child a child of a recursive node generated by removing a vertex from $G$ (i.e., in line 15). For a node $Z \in T$, we call a path $P$ from $Z$ to a leaf in $T$ obtained by only right children the right path of $Z$ (see Fig. 2 for an example). We show that the right path of $Y$ has at least $d_{G_X}(z) - 2k$ nodes. If it holds, by charging the $O(d_{G_X}(z))$ time cost divided equally on each node of the path, it amounts to $O(1)$ per each node, so the amortized time complexity of $X$ becomes $O(k^2)$ whereas the complexity of all other nodes is not changed. Since $d_{G_X}(z) \ge 3k$ and $|In_X| < k - 1$, $N_{G_X}(In_X \cup \{z\})$ has at least $d_{G_X}(z) - |In_X| \ge 2k + 2$ vertices. Notice that, for a node $Z$, if $N_{G_Z}(In_Z)$ has $k - |In_Z|$ vertices, there is no mandatory vertex.

Therefore, by picking and removing $k$ vertices in $N_{G_X}(In \cup \{z\})$, we cannot create new mandatory vertices; this means that the right path of $Y$ has at least $d_{G_X}(z) - 2k \ge k$ nodes. As each node is charged at most once, the time complexity of each node is $O(k^2)$. We then conclude that Algorithm 2 has total time complexity of $O(N_i \cdot k^2)$.

We next consider the space complexity. Let $X$ be a node and $Y$ be a child of $X$. In each recursive call, it is sufficient to store the difference between $In_X$ and $In_Y$ and $G_X$ and $G_Y$. It is clear that the sum of the difference between $In_X$ and $In_Y$ is bounded by $k$ and the difference between $G_X$ and $G_Y$ is $O(d(z))$, where $z$ is a removed vertex. Therefore, the total space complexity is bounded by $O(n + m)$. □

### 3.1.3 Bounded-Degree Graphs

The focus of the above analysis is to provide bounds that depend only on $k$ and not on the size of the graph $G$. As a byproduct, it is worth mentioning that the time complexity of this algorithm can be formalized more tightly for bounded-degree graphs, i.e., graphs

<figure><img src="image_7.png" /></figure>

<footnote n="3">³ We could also use $|In| = k$ as the base case, and the overall time complexity would not change. However, the time complexity analysis would become more difficult to follow, and we would introduce one additional level of recursion which we think it is useful, and meaningful, to avoid.</footnote>
<figure><img src="image_8.png" /><figcaption>**Fig. 2** Amortizing the cost of the recursive call X on the right path of Y: we charge $O(1)$ to each call on the nodes highlighted by the bracket. These calls are at least $d_{G_X}(z) - 2k$, so we can amortize the $O(d_{G_X}(z))$ cost on them</figcaption></figure>

where the maximum degree $\Delta$ is bounded by a constant. In the analysis in Theorem 4, we consider that the time complexity of finding a mandatory vertex is $O(k^2)$. From Lemma 2, it can be done in $O(k \cdot \min\{k, \Delta\})$ time. Moreover, since removing one vertex can be done in $O(\Delta)$ time, each recursive call can be done in $O(k \cdot \min\{k, \Delta\})$-time without an amortized analysis. We can thus show a tighter time complexity bound by taking this into account.

**Theorem 5** *Algorithm 2 runs in $O(N_i \cdot k \cdot \min\{k, \Delta\})$ time, where $N_i$ is the number of $k$-graphlets in $G$ that contain $In = v_i$. Thus, if $\Delta = O(1)$, Algorithm 2 runs in $O(k \cdot N_i)$ time.*

*Proof* The bottlenecks of Algorithm 2 are the deletion of a vertex, that can be trivially done in $O(\Delta)$ time, and the identification of mandatory edges, that by Lemma 2 takes $O(\min\{k, \Delta\})$ time. Therefore, each recursive call can be performed in $O(k \cdot \min\{k, \Delta\})$ time and the statement holds. □

## 3.2 Generating All *k*-Graphlets Using Algorithm 2

Algorithm 2 enumerates all *k*-graphlets in *G* that contain a specific set of vertices *In*, in *O*(k²) amortized time. It remains to see how to generate instances for it, i.e., how to generate all *k*-graphlets of *G* while retaining the same amortized time complexity. To do this we rely on Algorithm 3: Observe how vertices *v*₁, ..., *v*n are considered in a *reversed Breadth-First Search (BFS)* order, meaning we can perform a BFS from any
arbitrary vertex, write down the vertices in the order they are found in, then reverse this order. The advantage is that every suffix $v_i$, ..., $v_n$ is a connected subgraph, so it will always allow finding a k-graphlet as long as there are at least k vertices left (which is why we stop at $i = n - k + 1$). We can now prove the overall complexity for k-graphlet enumeration:

**Algorithm 3:** Generate all k-graphlets of a graph G using Algorithm 2 as subroutine.

**Input:** A connected graph G = (V, E), a positive integer k
**Output:** All k-graphlets.
1 **Function** Gen-Ins (G = (V, E), k)
2 &nbsp;&nbsp;&nbsp;&nbsp;Let $v_1, ..., v_n$ be a reversed BFS order of V
3 &nbsp;&nbsp;&nbsp;&nbsp;G₀ ← G
4 &nbsp;&nbsp;&nbsp;&nbsp;**for** i = 1, 2, ..., (n - k + 1) **do** // Skip the final k - 1 vertices
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**ENUM-V** (Gᵢ₋₁, {$v_i$}, k)
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Gᵢ ← Gᵢ₋₁ - {$v_i$}

**Theorem 6** Let $G = (V, E)$ be a connected graph and $k$ a positive integer. We can enumerate all $k$-graphlets in $G$ in $O(n+m+k^2 \cdot N)$ total time and $O(n+m)$ space, where $N$ is the number of solutions.

**Proof** We show that we can enumerate all *k*-graphlets using Algorithm 2 as a subroutine. Firstly, the reverse BFS order is computed with a simple BFS which takes $O(n+m)$ time. Then, for each *i*, we enumerate $S_i = S(G_{i-1} = G - \{v_1, ..., v_{i-1}\}, \{v_i\}, k)$. By the reversed BFS order, $G_{i-1}$ is a connected graph and thus will contain at least one solution (i.e., *k*-graphlet) as long as it has at least *k* vertices, i.e., for $i < n - k$, which are the values of *i* we consider.

We can thus enumerate all solutions in the set above by calling ENUM-V ($G_{i-1}$, {$v_i$}, $k$), which by Theorem 4 runs in $O(k^2 \cdot N_i)$ time, where $N_i = |S(G_i, \{v_i\}, k)|$.

Finally, observe how the various $S_i$ are a partition of the total set of solutions $S(G, \emptyset, k)$: indeed for any graphlet $g$, let $v_j$ be the first vertex of $g$ in the reverse BFS order; by definition of $S$ we have $g \in S(G_{j-1}, \{v_j\}, k)$. Moreover, $g$ cannot be in any other $S_h$ as if $h < j$ the graphlets found contain $v_h \notin g$, and if $h > j$ the graphlets found cannot contain $v_j$, as it is not in $G_{h-1}$. Thus $\cup_{i \in \{1, \dots, n-k+1\}} S_i = S(G, \emptyset, k)$, meaning Algorithm 3 will enumerate all $k$-graphlets of $G$ in $O(n+m+k^2 \cdot N)$ total time, i.e., $O(k^2)$ amortized time per solution. The space consumption of the whole strategy is $O(n+m)$, needed by Algorithm 2 by Theorem 4, as Algorithm 3 does not require asymptotically more space. □

We remark that, as shown in Theorem 5, the amortized cost is actually $O(k \cdot \min\{k, \Delta\})$, which technically could be lower than $O(k^2)$, although this is likely to be the case only in bounded-degree graphs.

<figure><img src="image_9.png" /></figure>
# 4 Enumeration of Edge $k$-Graphlets and $k$-Subtrees

In this section we address the problem of enumerating all edge $k$-graphlets for a given graph $G$. We observe that we can transform this problem into the $k$-graphlet enumeration presented in Sect. 3 by replacing $G$ with its line graph (which represents the adjacency between the edges of $G$ rather than between its nodes) [45]. This gives an amortized $O(k^2)$-time algorithm for enumerating all edge $k$-graphlets, but we are able to achieve a better complexity for this task, namely $O(k)$ amortized time per solution and $O(n+m)$ overall space. A slight variation of what we propose in this section also gives an enumeration algorithm for all $k$-subtrees with the same time and space complexity.

For ease of reading, we summarize the key operations of the algorithm:

* We use binary partition, where we select an edge $e$ and enumerate (i) all solutions containing $e$, then (ii) all solutions not containing $e$.

* We select $e$ so that the partial solution $In$ chosen so far is connected.

* Every time we select or exclude an edge, we identify special types of edges (*unnecessary, mandatory, far*) and process them with dedicated efficient strategies, that allow us to amortize the time complexity via push-out amortization.

## 4.1 Trimming Mandatory and Unnecessary Edges

In the following, given a graph $G = (V, E)$ and two disjoint sets $In, Ex \subseteq E$ of its edges, such that $G[In]$ is connected, we denote by $S(G, In, Ex, k)$ the set of edge $k$-graphlets in $G$ that contain $In$ and do not contain $Ex$. We denote by $V_{In}$ the set of vertices $V(G[In])$, and we recall that $V(G[In])$ contains all and only the vertices that are incident to at least one edge in $In$.

As $S(G, In, Ex, k) = S(G - Ex, In, \emptyset, k)$, we can simply ignore $Ex$ and hereafter use the reduced notation $S(G, In, k)$, and denoting the exclusion of a set of edges $Ex$ by simply removing them from $G$, i.e., $S(G - Ex, In, k)$. Recall that the removal of $Ex$ can be done in $O(|Ex|)$ time as remarked in Sect. 2.2.

Moreover, as edges from $G$ are removed, some edges may become *mandatory*: an edge $e$ is mandatory if the connected component in $G - e$ containing $V_{In}$ has less than $k$ edges (hence, $e$ must be part of all solutions containing $G[In]$). In principle, we could immediately add all mandatory edges directly to $In$, however, since we want to preserve $In$ to be a connected subgraph, the algorithm will only add the mandatory edges adjacent to $V_{In}$ (and iteratively add any mandatory edge that may become adjacent to $V_{In}$ in this process). While all mandatory edges must eventually be added to $In$, it is not necessary to do this immediately, as by only recurring into instances that have at least one solution, we will always finally reach a point where all the mandatory edges are adjacent to $V_{In}$ and are thus added to $In$. Let us consider the complexity of this operation:

We also want the algorithm to remove *unnecessary edges*: these are the edges that cannot be part of solutions containing $In$, as reaching them would require including more than $k$ edges. We define these as edges $e$ such that $dist(V_{In}, e) \ge k - |In|$, i.e.,
those whose distance from the closest vertex of $V_{In}$ to an endpoint of $e$ is at least $k - |In|$.

We call the identification and removal of unnecessary edges from $G$, as well as the (iterative) addition to $In$ of all mandatory edges adjacent to $V_{In}$, the trimming operation, and denote it by $\text{trim}(G, In, k)$.

More formally, the operation $\text{trim}(G, In, k)$ will return a pair $(H, In')$ where $In'$ is $In$ plus the mandatory edges that were adjacent to $V_{In}$, and $H$ is the graph obtained by removing the unnecessary edges from $G$, i.e., $E(H) = \{e \in E(G) | \text{dist}(V_{In'}, e) \ge k - |In'|\}$. We now show that this operation can be performed in $O(|E(H)|)$ time.

**Lemma 4** *Removing unnecessary edges in the instance $G$, $In$, $k$ can be performed in $O(|E(H)|)$ time, where $H$ is the graph obtained after removing such edges.*

*Proof* We show how to find the edges of $H$ in $O(|E(H)|)$ time, from which we can directly construct a copy of $H$. Firstly, all edges of $In$ are part of $H$. Moreover, if $|In| = k$ then there is no other edge and we are done; otherwise, as $|In| \le k$, any edge neighboring $In$ can potentially be added and thus will be part of $H$.

To find the remaining edges of $H$ let us contract all edges of $In$: as contracting an edge $\{x, y\}$ can be done in either $O(d(x))$ or $O(d(y))$ (see Sect. 2.2), we can complete the operation in $\sum_{v \in V_{In}} (d(v))$ time by choosing one arbitrary vertex $r \in V_{In}$ and iteratively contracting every edge $\{r, x\} \in In$ adjacent to $r$ in $O(d(r))$ time. Indeed since $In$ is connected, this will finally contract all its edges, and by the above observation all edges incident to $V_{In}$ are part of $H$, so $\sum_{v \in V_{In}} (d(v)) \le |E(H)|$.

Let $r$ be the vertex obtained by contracting $In$: We can now perform a breadth-first search from $r$ limited to distance $k - |In|$, which will identify all edges that belong to $H$ without traversing any of the farther away ones that do not, i.e., we can identify all edges of $H$ in $O(|E(H)|)$ time. $\square$

Now it is crucial to observe that, by definition, any edge that is mandatory cannot be also unnecessary. This means that the trimming operation can first remove unnecessary edges, obtaining $H$, and only then add the mandatory ones to $In$. Moreover, adding the mandatory edges does not increase distances from $V_{In}$, so it does not in turn create more unnecessary edges, and there is no need to reiterate the process. Thus, given $H$, we now focus on how to process the mandatory edges:

**Lemma 5** *Iterative identification and addition to $In$ of all mandatory edges adjacent to $V_{In}$, in the instance $H$, $In$, $k$, can be performed in $O(|E(H)|)$ time.*

*Proof* Firstly, if $|E(H)| = k$ then all edges are mandatory and we are done. Otherwise, any mandatory edge $e$ must be a *bridge*, i.e., an edge whose removal disconnects the graph, causing the loss of more than just $e$. In the following let us call the number of edges unreachable from $In$ when removing $e$ the *loss of $e$*.

We can identify all bridges in $O(|E(H)|)$ time [43], and these actually give us a tree-like decomposition where nodes are 2-edge-connected component (2ECC), and they are connected by the bridges.

Choose as root of this tree an arbitrary 2ECC that contains at least one node of $V_{In}$, and let us proceed in a bottom up way: for each leaf component $C$, its size is exactly

<figure><img src="image_10.png" /></figure>
the loss of the bridge connecting *C* to the tree (plus one, for the bridge itself). Going up, each internal component will cause a loss equal to its own size, plus the size of all its children bridges, which we have already computed in the bottom-up procedure. Of course, once we find a bridge in *In* or a component containing edges of *In* we can stop in this subtree since they cannot be removed. Clearly, a bridge is mandatory if its loss is more than |*E*(*H*)| − *k*, thus we can immediately label every such bridge as mandatory. This process takes *O*(|*E*(*H*)|) time as 2ECC are disjoint and the size of each is only computed once.

Finally, we go top-down from the components containing vertices in $V_{In}$ and add to $In$ all mandatory bridges adjacent to $V_{In}$, as well as iteratively the mandatory bridges adjacent to them (as they became part of $In$). This part also takes $O(|E(H)|)$ time as it can be done via a breadth-first search. This completes the proof. □

From Lemmas 4 and 5 we immediately obtain the following:

**Corollary 6** *The trimming operation trim(*G*, *In*, *k*), i.e., iterative addition of mandatory edges adjacent to *V*<sub>*In*</sub>, and removal of unnecessary edges, can be performed in *O*(|*E*(*H*)|) time, where *H* is the graph obtained from *G* after removing unnecessary edges. Note that |*E*(*H*)| ≤ |*E*(*G*)|.*

For this reason, in the rest of this section we focus on the problem of enumerating the edge *k*-graphlets of a generic instance *S*(*G*, *In*, *k*), with the understanding that any excluded edges (i.e., *Ex*) and unnecessary edges will be handled by the trimming operation. We say that an instance is *trimmed* if it has no unnecessary edges and *Ex* = ∅.

## 4.2 Far Edges

Given an instance of *G*, our partially formed solution *In* and *k*, our goal is to enumerate *S*(*G*, *In*, *k*). However, to optimize the running time, we enumerate some of the solutions with a different strategy, using *far edges*.

We say that an edge *e* is a *far edge* if $dist(V_{In}, e) = k - |In| - 1$, and define the set of all far edges as $E_{far} = \{e \in E | dist(V_{In}, e) = k - |In| - 1\}$. Intuitively, this means that the only way to find a solution including the edge *e*, is to include a shortest path from $V_{In}$ to *e*. Thus we can transform the problem of enumerating the solutions that contain a far edge into a shortest-path enumeration problem, then remove $E_{far}$ from *G* to enumerate the rest.

Formally, we partition $S(G, In, k)$ into two disjoint sets, which are enumerated separately:

* $S_{far}(G, In, k)$ is the set of solutions in $S(G, In, k)$ that contain a far edge.

* $S_{near}(G, In, k)$ are the remaining solutions, i.e., $S(G, In, k) \setminus S_{far}(G, In, k)$.

**Observation 7** *Let $H$ be an edge $k$-graphlet in $S_{far}(G, In, k)$. Then $|H| - e$ must be a shortest path between $V_{In}$ and an endpoint of $e$.*

From Observation 7, we can enumerate all edge *k*-graphlets in $S_{far}(G, In, k)$ using an algorithm for enumerating all shortest paths. Enumeration of all shortest paths can
be done in constant amortized time with linear time preprocessing (see [46, Section 4.1]). The authors of [46] gave a constant amortized time enumeration of all s-t paths on DAGs. On the other hand, our problem is multi-source and multi-sink shortest path enumeration, but it is known that this problem can be reduced to a s-t path enumeration on DAGs (see, for instance, [35]).

As $S_{\text{far}}(G, In, k)$ can be enumerated efficiently, we then focus on the enumeration of $S_{\text{near}}(G, In, k)$. Firstly, observe that we can find $S_{\text{near}}(In, k, r)$ by simply removing $E_{\text{far}}$ from $G$:

**Lemma 8** $S_{\text{near}}(G, In, k) = S(G - E_{\text{far}}, In, k)$.

*Proof* For any $H \in S_{\text{near}}(G, In, k)$, $H$ cannot be in $S_{\text{far}}(G, In, k)$ as it does not contain any edge from $E_{\text{far}}$; hence, $H \in S(G - E_{\text{far}}, In, k)$. Vice versa, for any $H \in S(G - E_{\text{far}}, In, k)$, $H$ is contained in $S_{\text{near}}(G, In, k)$ by definition. $\square$

By Lemma 8, it suffices to perform $\text{trim}(G - E_{\text{far}}, In, k)$ and enumerate all edge $k$-graphlets in the resulting trimmed instance.

## 4.3 Partition Strategy

Algorithm 4 summarizes the partition strategy, where we organize the computation so that the push-out amortization can be applied. Recall that we select $e$ so that $In$ stays connected, and that we only immediately add to $In$ the mandatory edges adjacent to $V_{In}$.

A key idea to make the amortization work are *heavy edges*: we say that an edge $e$ is *heavy* if the number of unnecessary edges in $G - e$ is at least $|E|/2$.

**Lemma 9** Let $G, In, k$ be a trimmed instance. $\Gamma(V_{In})$ has at most one heavy edge, and least one non-heavy edge.

*Proof* Firstly, since the instance is trimmed, $\Gamma(V_{In})$ has no mandatory edges, and has at least 2 edges (if there was only one edge, it would be mandatory to use it). Observe also how $G$ has initially no unnecessary edges, so the unnecessary edges that determine whether an edge $e$ is heavy or not are only the ones created by the removal of $e$ itself.

Suppose that $\Gamma(V_{In})$ has two heavy edges $e \neq f$. Let $U_e$ be the unnecessary edges in $G - \{e\}$, and $U_f$ be the unnecessary edges in $G - \{f\}$. We first prove that $U_e$ and $U_f$ are disjoint: if an edge $g$ is in $U_e$, since it was not unnecessary in $G$, it means in $G$ it had a shortest path towards $V_{In}$ that used $e$; this shortest path clearly cannot also use $f$, as just one between the edges $e$ and $f$ is sufficient to connect to $V_{In}$. Thus, this shortest path is not broken by the removal of $f$, meaning $g \notin U_f$. This means $U_e \cap U_f = \emptyset$. Moreover, $e$ and $f$ are directly adjacent to $V_{In}$ so $e \notin U_f$ and $f \notin U_e$.

Let $m = |E(G)|$. We have $|U_e| + |U_f| \leq m - 2$ as $e$ and $f$ themselves do not belong to these sets; this contradicts that both $e$ and $f$ can be heavy as it would imply $|U_e| + |U_f| \geq m/2 + m/2 = m$. Thus there is at most one heavy edge. Finally, as we observed $\Gamma(V_{In})$ has at least 2 edges, it follows that at least one is non heavy. $\square$

The following theorem establishes a bound on the space consumption of our strategy.
**Algorithm 4:** Given a graph *G*, a set *In* of its edges inducing a connected subgraph, and a non-negative integer *k*, the algorithm enumerates all edge *k*-graphlets that contain *In*.

**Input:** Graph *G* = (*V*, *E*), edge set *In* ⊆ *E*, non-negative integer *k*

**Output:** All edge *k*-graphlets of *G* that contains *In*

1 **Function** Enum-E(*G* = (*V*, *E*), *In*, *k*):

2 **if** |*In*| = *k* **then** Output *In* and **return**

3 **if** |*In*| = *k* − 1 **then**

4 **[** **for** *f* ∈ Γ(*V*<sub>*In*</sub>) **do** output *In* ∪ {*f*}; **return**

5 Enumerate all solutions that contain a far edge. // See Section 4.2

6 *G* ← *G* − *E*<sub>*far*</sub> // Remove all far edges

7 Let *e* be a non-heavy edge in Γ<sub>*G*</sub>(*V*<sub>*In*</sub>) // *e* exists by Lemma 9

8 ⟨*H*′, *In*′⟩ ← *trim*(*G*, *In* ∪ {*e*}, *k*)

9 ** Enum-E(H', In', k) // Solutions containing e**

10 ⟨*H*'', *In*''⟩ ← *trim*(*G* − {*e*}, *In*, *k*)

11 ** Enum-E(H'', In'', k) // Solutions not containing e**

12 **Function** *trim*(*G*, *In*, *k*):

13 **while** Γ(*V*<sub>*In*</sub>) contains a mandatory edge **do**

14 Let *e* be a mandatory edge in Γ(*V*<sub>*In*</sub>)

15 *In* ← *In* ∪ {*e*}

16 *E*<sub>*H*</sub> ← {*e* ∈ *E*(*G*)|*dist*(*V*<sub>*In*</sub>, *e*) < *k* − |*In*|}

**Theorem 7** *Algorithm 4 computes S(*G*, *In*, *k*) using *O*(*n* + *m*) space.*

**Proof** By Observation 7 and Lemma 8, we can enumerate all solutions in $S_{\text{far}}(G, In, k)$ and $S_{\text{near}}(G, In, k) = S(G - E_{\text{far}}, In, k)$, respectively. By Lemma 9, $\Gamma(V_{In})$ contains at least one non-heavy edge $e$. Moreover, when $\Gamma(V_{In})$ has only one edge, we add this edge to $In$ until $\Gamma(V_{In})$ contains at least two edges (i.e. we follow the chain of mandatory edges). Thus, we can partition $S(G - E_{\text{far}}, In, k)$ into two sets using a non-heavy edge. Moreover, in each node, we store only the set of edges added to $In$ and the set of removed edges. Therefore, the total space requirement is $O(n+m)$ at any time. $\square$

## 4.4 Time Complexity Analysis

We now show how to apply the push-out (PO) amortization to state the time complexity analysis of Algorithm 4. We first show that, given a recursive node *X* corresponding to Enum-E(*G* = (*V*, *E*), *In*, *k*), the algorithm runs in amortized *O*(*m*) time, i.e., *O*(*m* · *N*) time if the instance received at the root is already trimmed, where *m* = |*E*(*G*)|. We will later improve this to *O*(*k*) amortized time but this is a necessary first step.

By Corollary 6 and what stated in Sect. 4.2, The trimming operation and the enumeration of shortest path line 5 can be performed in $O(m + |ch(X)|)$ time, where $|ch(X)|$ is the number of recursive children of *X* (which is 2 for the binary partition, plus one for each shortest path enumerated on line 5.)
As the recursive subtree is a tree where every recursive node has at least 2 children, i.e., the total number of recursive nodes is at least half of the total number of leaves, and each leaf corresponds to one of the *N* solutions, the total cost is $O(m \cdot N)$.

Now, our goal is to further improve the analysis, and show that Algorithm 4 runs in amortized $O(k)$ time. Each leaf node demands $O(k)$ time since each leaf node just outputs a solution. Let us formalize the cost of internal nodes:

**Lemma 10** *The time required a recursive call $X = \text{Enum-E}(G, In, k)$, ignoring the cost if its two recursive children, is $O(m_X + |ch(X)|)$, where $m_X = |E(G)|$ and $|ch(X)|$ is the total number of children (including the solutions generated by enumerating shortest paths to far edges).*

*Proof* Firstly, if triggered, Lines 2–4, take just $O(m_X)$ time. Then, line 5 takes $O(m_X + |ch(X)|)$ time as discussed in Sect. 4.2. Deleting $E_{\text{far}}$ also takes $O(m_X)$ time as edges take constant time each to delete. Finally, the two trimming operations take $O(|E(H)|)$ time each by Corollary 6, where $H$ is the resulting graph generated, which is a subgraph of $G$, so $|E(H)| \le m_X$. □

We will then show that each node $X$ satisfies the PO condition by setting $\alpha = \beta = 5/4$. To do so, we define $c^*$ as an arbitrary constant that is larger than the constant hidden in the big $O$ notation for computation time at internal nodes and at leaf nodes. Thus, we assume that each internal node $X$ takes $c^*(m_X + |ch(X)|)$ time and each leaf node $T$ takes $c^* \cdot k$ time.

It is worth noting that $O(k)$ amortized time is trivially obtained on instances where the graph has $O(k)$ edges:

**Observation 11** *When $m_X = O(k)$, Algorithm 4 runs in amortized $O(k)$ time since, as shown above it achieves amortized $O(m)$ time where $m$ is the size of the graph, and in this case the size of the graph received by the recursive call $X$ is indeed $m_X \le 4k$ and thus $O(k)$, and in this case we have $m_X = O(k)$.*

Thus, although we do not actually use this assumption, we observe that the amortization is only really necessary when $m_X = \omega(k)$.

Next, let us consider lower bounds for the size of each trimmed instance received by a child during the recursion, analyzing the various operations that change the instance. We first consider how trimming after removal of far edges does not remove further edges:

**Lemma 12** *Let $G, In \neq \emptyset, k$ be a trimmed instance, and $E_{\text{far}}$ its far edges. Then, $\text{trim}(G - E_{\text{far}}, In, k)$ has at least $|E(G)| - |E_{\text{far}}|$ edges.*

*Proof* From the definition of the operation $\text{trim}()$, we remove all unnecessary edges. Observe how a far edge could only be reached by $In$ by adding a shortest path to $e$ and $e$ itself; any edge farther away from $In$ could not be added as it would be unnecessary (thus not present in the trimmed instance). This means that no edge would require $e$ in order to reach $In$, and thus the removal of the far edge $e$ does not cause any other edge to become unnecessary (or far), and thus nothing other than $E_{\text{far}}$ is removed by $\text{trim}(G - E_{\text{far}}, In, k)$. □

<figure><img src="image_11.png" /></figure>
Next, we show that adding one edge to *In* does not change the size of a graph when an instance is trimmed:

**Lemma 13** Let $G, In, k$ be a trimmed instance with no far edges, i.e., $E_{\text{far}} = \emptyset$. For an edge $e \in \Gamma(In)$, the graph obtained by $\text{trim}(G, In \cup \{e\}, k)$ has $|E(G)|$ edges.

**Proof** As $\text{trim}()$ removes only unnecessary edges, it is sufficient to show that no edge becomes unnecessary: indeed, an edge is unnecessary if its distance from $V_{In}$ is at least $|In| - k$. However, every edge that is not a far edge, has distance from $In$ smaller than $|In| - k - 1$, i.e., at most $|In| - k - 2$. Adding $e$ increase $|In|$ by one, thus the new distance from $In \cup \{e\}$, in the worst case, will be at most $|In| - k - 2 + 1 = |In| - k - 1$. In other words, the addition of $e$ may create far edges, but not unnecessary edges. □

Finally, we observe the impact of $\text{trim}()$ when removing a non-heavy edge in a previously trimmed instance, which follows immediately from the definition of heavy edge.

**Observation 14** Let $G, In, k$ be a trimmed instance, and let $e \in \Gamma(V_{In})$ be a non-heavy edge. Then, the graph obtained by $\text{trim}(G - \{e\}, In, k)$ has at least $|E(G)|/2$ edges.

Now, we are ready to give our analysis.

**Lemma 15** Let $X$ be a node in the recursion tree of Algorithm 4. Moreover, let $(G_X, In_X, k_X)$ be an instance corresponding to $X$. Then, $X$ satisfies the PO condition (Theorem 1) by setting $\alpha = \beta = 5/4$ and $T^* = O(k)$.

**Proof** Let $F_X$ be the set of far edges in $G_X$. The number of children of $X$, i.e., $|ch(X)|$, is at least $|F_X| + 2$ (at least one per far edge, plus two nested recursive calls). The graph obtained by $\text{trim}(G - F_X, In, k)$ has at least $|E_X| - |F_X|$ edges by Lemma 12, and this gets passed to the children recursive calls. Lemma 9 tells us that there is always a non-heavy edge $e$ that we can consider, thus we can give lower bounds to the size of the graph received by the children recursive calls. The child on Line 9 adds $e$ so by Lemma 13 has size $|E_X| - |F_X|$. The child on Algorithm 11 removes $e$ so by Observation 14 has size $\geq (|E_X| - |F_X|)/2$, each child derived from a far edge is a leaf, which takes $O(k)$ time to simply output their solution, and thus we have at least $|F_X|$ children of size $O(k)$ each. Recalling as noted above that the constant factors in the big $O$ notation are denoted by $c^*$, the cost of each recursive call given by lemma 10, and that $k \geq 2$ (as $k = 1$ is a trivial problem), putting all together we have that the sum of running time of the children $ch(X)$ of $X$ is:

$$ 
\begin{align*}
\sum_{Y \in ch(X)} T(Y) &\geq c^*(|E_X| - |F_X|) + c^*(|E_X| - |F_X|)/2 + c^* \cdot k \cdot |F_X| \\
&= \frac{3}{2}c^*|E_X| - \frac{3}{2}c^*|F_X| + c^* \cdot k \cdot |F_X| \\
&= \frac{3}{2}c^*|E_X| + c^*\left(k - \frac{3}{2}\right)|F_X| \\
&\geq \frac{3}{2}c^*|E_X|
\end{align*}
$$
We next analyze the term $\alpha T(X) - \beta(|ch(X)| + 1)T^*$ as follows. Recall that the number of children of X obtained by enumeration of far edges is at least $|F_X|$, but could be exponentially more, let this number be $|F_X| + \gamma$, with $\gamma \ge 0$, and recall that X has two more children obtained by recursive calls, finally, recall that the cost of a leaf is assumed to be $T^* = O(k) = c^*k$.

$$ 
\begin{aligned}
\alpha T(X) - \beta(|ch(X)| + 1)T^* &= \alpha c^*(|E_X| + |F_X| + \gamma) - \beta(2 + |F_X| + \gamma + 1)c^*k \\
&= \frac{5}{4}c^*(|E_X| + |F_X| - k|F_X| + \gamma - k\gamma - 3) \\
&= \frac{5}{4}c^*(|E_X| - (k-1)|F_X| - (k-1)\gamma - 3) \\
&\le \frac{5}{4}c^*|E_X|
\end{aligned}
$$

Where for simplicity we ignored negative factors in the last step. Therefore, we have

$$ \sum_{Y \in ch(X)} T(Y) \ge \frac{3}{2}c^*|E_X| > \frac{5}{4}c^*|E_X| \ge \alpha T(X) - \beta(|ch(X)| + 1)T^* $$

We can thus conclude that the PO condition holds for every recursive node of Algorithm 4, with $\alpha = \beta = 5/4$ and $T^* = O(k)$. □

Therefore, each internal node satisfies the PO condition and we obtain the following result.

**Theorem 8** Algorithm 4 runs in total $O(n + m + k \cdot N)$ time and $O(n + m)$ space if $In \ne \emptyset$, where N is the number of solutions. If the instance received at the root of the recursion tree is already trimmed, Algorithm 4 runs in $O(k \cdot N)$ time.

## 4.5 Generating All Edge k-Graphlets Using Algorithm 4

As we did for the vertex k-graphlets, we now combine everything together to show that we can enumerate all edge k-graphlets in $O(n + m + k \cdot N)$ total time. To this end, we show our instance generation algorithm in Algorithm 5. It essentially iterates over all edges, using each edge $e_i$ as the first building block of a potential solution; however, as Enum-E assumes the input graph to be trimmed, it also performs the trimming operation before calling it. Finally, note how we consider the edges in a reversed BFS order of E: this means performing a BFS from an arbitrary starting vertex v, writing the edges down in the order in which they are found, and finally reversing the sequence. This order has the significant advantage that every suffix of it corresponds to a connected graph (as all remaining edges $e_i, \dots, e_m$ are still able to reach v). This means that every instance generated will have at least k edges reachable from $e_i$, except for when less than k edges are left in the graph (which is why we stop at $i = m - k + 1$). By combining Algorithms 4 and 5, we obtain the following theorem.
**Algorithm 5:** Generate all edge *k*-graphlets of a graph *G* using Algorithm 4 as subroutine.

**Input:** A connected graph $G = (V, E)$, a positive integer $k$
**Output:** all edge $k$-graphlets.
1 **Function** Gen-Ins ($G = (V, E)$, $k$)
2 &nbsp;&nbsp;&nbsp;&nbsp;Let $e_1, \dots, e_m$ be a reversed BFS order of $E$
3 &nbsp;&nbsp;&nbsp;&nbsp;$G_0 \leftarrow G$
4 &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 1, 2, \dots, (m-k+1)$ **do** // We can skip the final $k-1$ edges
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(H, In) \leftarrow \text{trim}(G_{i-1}, \{e_i\}, k)$
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;** Enum-E** $(H, In, k)$
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$G_i \leftarrow G_{i-1} - \{e_i\}$

**Theorem 9** Let $G$ be a connected graph and $k$ be a positive integer. We can enumerate all edge $k$-graphlets in $O(n+m+k \cdot N)$ time and $O(n+m)$ space, where $N$ is the number of solutions.

**Proof** The proof follows from the same argument used in Theorem 6. As computing the reverse BFS order requires performing a BFS, which takes $O(n+m)$ time just once. The removal of $e_i$ on Line 7 takes constant time so the total contribution of this line is $O(m)$ time. Finally, we need to call `trim`($G_{i-1}, \{e_i\}, k$), which produces the pair $(H, In)$ in $O(|E(H)|)$ time by Corollary 6: we can actually just charge this cost onto the recursive call $X = \text{ Enum-E}(H, In, k)$ generated, as by Lemma 10, $X$ already takes $O(|E(H)| + |ch(X)|)$ time, so this does not alter its complexity. Finally, Theorem 8 shows that ` Enum-E()` respects the PO condition with $T^* = O(k)$, which by Theorem 1 means that it achieves $O(k)$ amortized time per graphlet enumerated. The running time is thus $O(n+m+k \cdot N)$ total time, where $N$ is the number of edge $k$-graphlets contained in $G$. $\square$

## 4.6 Modifications for *k*-Subtrees Enumeration

In this section, we propose an algorithm for enumerating all *k*-subtrees in a graph, obtained by small modifications of Algorithm 4. Let *X* be a node of the recursion tree as seen in the previous sections, *G*<sub>*X*</sub> be the associated graph, *In*<sub>*X*</sub> be a set of edges, and *k* be an integer. The main difference between this algorithm, and Algorithm 4 lies in the partition strategy. Indeed, for an edge *e* = {*u*, *v*} ∈ Γ<sub>*G*<sub>*X*</sub></sub>(*In*<sub>*X*</sub>) such that *u* is incident to any edge of *In*<sub>*X*</sub>, an edge that connects vertices *v* and a vertex in *G*<sub>*X*</sub>[*In*<sub>*X*</sub>] cannot be added to *In*<sub>*X*</sub> ∪ {*e*} (otherwise it would form a cycle), hence we remove such edges from *G*<sub>*X*</sub>. The correctness of this algorithm can be shown using the same arguments adopted in Sect. 4. We can also prove that the PO condition holds for this algorithm: in particular, when we add an edge *e* = {*u*, *v*} to *In*<sub>*X*</sub>, and there exist many edges that connect *v* and another vertex in *G*<sub>*X*</sub>[*In*<sub>*X*</sub>], we can generate all subproblems (i.e. children nodes in the recursion tree) in linear time. Therefore, we can enumerate also *k*-subtrees in *O*(*k*) amortized time, as stated in the following theorem.

**Theorem 10** Let $G$ be a graph and $k$ be an integer. We can enumerate all $k$-subtrees of $G$ in $O(n+m+k \cdot N)$ time and $O(n+m)$ space, where $N$ is the number of $k$-subtrees.
# 5 Conclusions and Future Work

We provided new algorithms for enumerating both vertex-induced and edge-induced subgraphs/subtrees in any simple, undirected graph, improving the state of the art for both problems. This improvement over the fastest known algorithms in the literature was possible by the use of both traditional amortized analysis and the more recent push-out amortized analysis. Our algorithms are the first to have time complexity depending solely on the size of the subgraph to be enumerated, i.e., $O(k^2)$ amortized time for $k$-graphlets and $O(k)$ amortized time for edge $k$-graphlets, in contrast with existing approaches that also include the size of the graph or its maximum degree in their complexity bounds.

The question on whether $O(k)$ amortized time is attainable for $k$-graphlets is still open, in contrast to what we did with edge $k$-graphlets/subtrees, because a $k$-graphlet can have a quadratic number of edges, making this open problem challenging.

**Acknowledgements** We wish to thank the anonymous reviewers for the detailed feedback that allowed us to improve the clarity of the paper. The work was partially supported by MUR PRIN 2022 project EXPAND: scalable algorithms for Exploratory Analyses of heterogeneous and dynamic Networked Data (#2022TS4Y3N).

**Author contributions** All authors have contributed equally to the work.

**Funding** Open access funding provided by ISTI - PISA within the CRUI-CARE Agreement.

**Data Availability** No datasets were generated or analysed during the current study.

# Declarations

**Competing interests** The authors declare no competing interests.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

# References

1. Lacroix, V., Fernandes, C.G., Sagot, M.-F.: Motif search in graphs: application to metabolic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 3(4), 360–368 (2006)

2. Ciriello, G., Guerra, C.: A review on models and algorithms for motif discovery in protein–protein interaction networks. Brief. Funct. Genom. 7(2), 147–156 (2008). https://doi.org/10.1093/bfgp/eln015

3. Yu, S., Feng, Y., Zhang, D., Bedru, H.D., Xu, B., Xia, F.: Motif discovery in networks: a survey. Comput. Sci. Rev. 37, 100267 (2020)

4. Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75–174 (2010). https://doi.org/10.1016/j.physrep.2009.11.002

5. Pržulj, N., Corneil, D.G., Jurisica, I.: Modeling interactome: Scale-free or geometric? Bioinformatics 20(18), 3508–3515 (2004). https://doi.org/10.1093/bioinformatics/bth436

<figure><img src="image_12.png" /></figure>
6. Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., Borgwardt, K.: Efficient graphlet kernels for large graph comparison. In: Artificial Intelligence and Statistics, pp. 488–495. PMLR (2009)

7. Kriege, N.M., Johansson, F.D., Morris, C.: A survey on graph kernels. Appl. Netw. Sci. 5(1), 6 (2020).
https://doi.org/10.1007/s41109-019-0195-3

8. Windels, S.F., Malod-Dognin, N., Pržulj, N.: Graphlet eigentralities capture novel central roles of genes in pathways. PLoS ONE 17(1), 0261676 (2022)

9. Aparício, D., Ribeiro, P., Silva, F., Silva, J.: Finding dominant nodes using graphlets. In: Complex Networks, pp. 77–89. Springer (2019)

10. Klymko, C., Gleich, D., Kolda, T.G.: Using triangles to improve community detection in directed networks (2014). arXiv preprint arXiv:1404.5874

11. Prat-Pérez, A., Dominguez-Sal, D., Brunat, J.M., Larriba-Pey, J.-L.: Shaping communities out of triangles. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management. CIKM '12, pp. 1677–1681. Association for Computing Machinery, New York, NY, USA (2012). https://doi.org/10.1145/2396761.2398496

12. Friggeri, A., Chelius, G., Fleury, E.: Triangles to capture social cohesion. In: 2011 IEEE Third International Conference on Privacy, Security, Risk and Trust and 2011 IEEE Third International Conference on Social Computing, pp. 258–265 (2011). https://doi.org/10.1109/PASSAT/SocialCom.2011.169

13. Jabbour, S., Mhadbhi, N., Raddaoui, B., Sais, L.: Triangle-driven community detection in large graphs using propositional satisfiability. In: 2018 IEEE 32nd International Conference on Advanced Information Networking and Applications (AINA), pp. 437–444 (2018). https://doi.org/10.1109/AINA.2018.00072

14. Chin, A.J., Gordon, G., MacPhee, K.J., Vincent, C.: Subtrees of graphs. J. Graph Theory 89(4), 413–438 (2018). https://doi.org/10.1002/jgt.22359

15. Zhang, S., Hu, M., Yang, J.: Treepi: A novel graph indexing method. In: 2007 IEEE 23rd International Conference on Data Engineering, pp. 966–975 (2007). https://doi.org/10.1109/ICDE.2007.368955

16. Gaüzère, B., Brun, L., Villemin, D.: Two new graphs kernels in chemoinformatics. Pattern Recogn. Lett. 33(15), 2038–2047 (2012). https://doi.org/10.1016/j.patrec.2012.03.020

17. Sun, D., Li, L., Liu, K., Wang, H., Yang, Y.: Enumeration of subtrees of planar two-tree networks. Appl. Math. Comput. 434, 127404 (2022). https://doi.org/10.1016/j.amc.2022.127404

18. Wasa, K.: Enumeration of enumeration algorithms. CoRR (2016). arXiv:1605.05102

19. Uno, T.: Constant time enumeration by amortization. In: Algorithms and Data Structures—14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5–7, 2015. Proceedings, pp. 593–605 (2015). https://doi.org/10.1007/978-3-319-21840-3_49

20. Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parameter-tractable algorithms. Inf. Process. Lett. 73(3–4), 125–129 (2000)

21. Damaschke, P.: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci. 351(3), 337–350 (2006). https://doi.org/10.1016/j.tcs.2005.10.004

22. Wernicke, S.: A faster algorithm for detecting network motifs. In: Casadio, R., Myers, G. (eds.) Algorithms in Bioinformatics, pp. 165–177. Springer, Berlin, Heidelberg (2005)

23. Wernicke, S., Rasche, F.: FANMOD: a tool for fast network motif detection. Bioinformatics 22(9), 1152–1153 (2006). https://doi.org/10.1093/bioinformatics/btl038

24. Pinar, A., Seshadhri, C., Vishal, V.: Escape: efficiently counting all 5-vertex subgraphs. In: Proceedings of the 26th International Conference on World Wide Web. WWW '17, pp. 1431–1440. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE (2017). https://doi.org/10.1145/3038912.3052597

25. Paredes, P., Ribeiro, P.: Towards a faster network-centric subgraph census. In: 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013), pp. 264–271 (2013). https://doi.org/10.1145/2492517.2492535

26. Kashani, Z.R.M., Ahrabian, H., Elahi, E., Nowzari-Dalini, A., Ansari, E.S., Asadi, S., Mohammadi, S., Schreiber, F., Masoudi-Nejad, A.: Kavosh: a new algorithm for finding network motifs. BMC Bioinform. 10(1), 318 (2009). https://doi.org/10.1186/1471-2105-10-318

27. Melckenbeeck, I., Audenaert, P., Colle, D., Pickavet, M.: Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations. Bioinformatics 34(8), 1372–1380 (2017). https://doi.org/10.1093/bioinformatics/btx758

28. Ribeiro, P., Paredes, P., Silva, M.E.P., Aparicio, D., Silva, F.: A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Comput. Surv. 54(2), 1–36 (2021). https://doi.org/10.1145/3433652
29. Ahmed, N.K., Neville, J., Rossi, R.A., Duffield, N.: Efficient graphlet counting for large networks. In: 2015 IEEE International Conference on Data Mining, pp. 1–10 (2015). https://doi.org/10.1109/ICDM. 2015.141

30. Komusiewicz, C., Sommer, F.: Enumerating connected induced subgraphs: improved delay and experimental comparison. Discrete Appl. Math. (2020). https://doi.org/10.1016/j.dam.2020.04.036

31. Conte, A., Grossi, R., Rucci, D.: Cage: cache-aware graphlet enumeration. In: Nardini, F.M., Pisanti, N., Venturini, R. (eds.) String Processing and Information Retrieval, pp. 129–142. Springer, Cham (2023)

32. Wang, S., Xiao, C., Casseau, E.: Algorithms with improved delay for enumerating connected induced subgraphs of a large cardinality. Inf. Process. Lett. 183, 106425 (2024). https://doi.org/10.1016/j.ipl. 2023.106425

33. Liu, X., Chen, Y.-Z.J., Lui, J.C., Avrachenkov, K.: Learning to count: a deep learning framework for graphlet count estimation. Netw. Sci. 9(S1), 23–60 (2021)

34. Read, R.C., Tarjan, R.E.: Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5(3), 237–252 (1975)

35. Birmelé, E., Ferreira, R., Grossi, R., Marino, A., Pisanti, N., Rizzi, R., Sacomoto, G.: Optimal listing of cycles and ST-paths in undirected graphs. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’13, pp. 1884–1896. Society for Industrial and Applied Mathematics, USA (2013)

36. Tsukiyama, S., Shirakawa, I., Ozaki, H., Ariyoshi, H.: An algorithm to enumerate all cutsets of a graph in linear time per cutset. J. ACM 27(4), 619–632 (1980)

37. Wasa, K., Uno, T.: Efficient enumeration of bipartite subgraphs in graphs. In: Computing and Combinatorics—24th International Conference, COCOON 2018, Qing Dao, China, July 2–4, 2018, Proceedings. Lecture Notes in Computer Science, vol. 10976, pp. 454–466. Springer, Cham, Switzerland (2018)

38. Kurita, K., Wasa, K., Uno, T., Arimura, H.: Efficient enumeration of induced matchings in a graph without cycles with length four. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E101-A(9), 1383–1391 (2018)

39. Wasa, K., Uno, T.: An efficient algorithm for enumerating induced subgraphs with bounded degeneracy. In: Kim, D., Uma, R.N., Zelikovsky, A. (eds.) Combinatorial Optimization and Applications, pp. 35–45. Springer, Cham (2018)

40. Kurita, K., Wasa, K., Uno, T., Arimura, H.: A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number. Theor. Comput. Sci. 874, 32–41 (2021). https://doi.org/10.1016/J.TCS.2021.05.008

41. Wasa, K., Kaneta, Y., Uno, T., Arimura, H.: Constant time enumeration of bounded-size subtrees in trees and its application. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) Computing and Combinatorics, pp. 347–359. Springer, Berlin, Heidelberg (2012)

42. Uno, T.: Two general methods to reduce delay and change of enumeration algorithms (2003)

43. Tarjan, R.E.: A note on finding the bridges of a graph. Inf. Process. Lett. 2(6), 160–161 (1974). https:// doi.org/10.1016/0020-0190(74)90003-9

44. Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372–378 (1973). https://doi.org/10.1145/362248.362272

45. Harary, F., Norman, R.Z.: Some properties of line digraphs. Rend. Circ. Mat. Palermo 9(2), 161–168 (1960). https://doi.org/10.1007/BF02854581

46. Conte, A., Grossi, R., Punzi, G., Uno, T.: A compact DAG for storing and searching maximal common subsequences. In: Iwata, S., Kakimura, N. (eds.) 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol. 283, pp. 21–12115. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2023). https:// doi.org/10.4230/LIPIcs.ISAAC.2023.21

<figure><img src="image_13.png" /></figure>
## Authors and Affiliations

Alessio Conte⁵ · Roberto Grossi⁵ · Yasuaki Kobayashi¹ · Kazuhiro Kurita³ · Davide Rucci⁶ · Takeaki Uno⁴ · Kunihiro Wasa²

<figure><img src="image_14.png" /></figure>

Davide Rucci
davide.rucci@isti.cnr.it

Alessio Conte
alessio.conte@unipi.it

Roberto Grossi
roberto.grossi@unipi.it

Yasuaki Kobayashi
koba@ist.hokudai.ac.jp

Kazuhiro Kurita
kurita@i.nagoya-u.ac.jp

Takeaki Uno
uno@nii.ac.jp

Kunihiro Wasa
wasa@hosei.ac.jp

1 Hokkaido University, Sapporo, Japan

2 Hosei University, Tokyo, Japan

3 Nagoya University, Nagoya, Japan

4 National Institute of Informatics, Tokyo, Japan

5 University of Pisa, Pisa, Italy

6 ISTI-CNR, Pisa, Italy