1]Hokkaido University, Sapporo, Japan2]Hosei University, Tokyo, Japan3]Nagoya
University, Nagoya, Japan4]National Institute of Informatics, Tokyo,
Japan5]University of Pisa, Pisa, Italy

# Enumerating Graphlets with Amortized Time Complexity Independent of Graph
Size

Alessio Conte<EMAIL_ADDRESS>Roberto Grossi<EMAIL_ADDRESS>Yasuaki Kobayashi<EMAIL_ADDRESS>Kazuhiro Kurita
<EMAIL_ADDRESS>Davide Rucci<EMAIL_ADDRESS>Takeaki Uno
<EMAIL_ADDRESS>Kunihiro Wasa<EMAIL_ADDRESS>[  [  [  [  [

###### 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 cost per solution 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 cost per solution 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^{2})$ 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 cost per solution 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, 2, 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 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_.

(a)

(b)

(c)

Figure 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$.

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, 11, 12, 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 as a
function of the output size. Specifically, let $N$ be the total number of
solutions found. If the overall cost is $O(\mathrm{poly}(|V|)+N\cdot f(k))$
time for some function $f()$, we say that the _amortized_ cost per solution is
$O(f(k))$.111$O(\mathrm{poly}(|V|))$ does not consider the amortized cost
since it is independent of $N$. 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 1, and $O(k)$ amortized time per edge
$k$-graphlet in 2. When compared to the state of the art discussed in Section
1.1, (i) we provide a faster cost per solution, 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 costs depends on $k$ alone.

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 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$ vertices222It 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]., each of these
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\leq 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 cost per solution. 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 in this paper belong to the
class of enumeration algorithms of for a given $k$, and have no limitations on
the value for $k$. Our algorithms improve the current state of the art from
roughly $O(k^{2}\Delta)$ cost per solution 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 cost per
solution.

##  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 Section 2.2, we also give a
technique for analyzing the amortized time complexity of enumeration
algorithms called a _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 $\left|\Gamma_{G}(v)\right|$ is called the _degree
of $v$_ and denote it as $d_{G}(v)$. Moreover, $\max_{v\in V}d_{G}(v)$ is the
_degree of $G$_ and denote it as $\Delta$. We drop the subscript when it can
be referred 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]\coloneqq N(v)\cup\\{v\\}$ and
$N[U]\coloneqq\bigcup_{u\in U}N(u)\cup U$.

A vertex sequence $P\coloneqq(v_{1},\ldots,v_{\ell})$ is a _path_ if for any
$1\leq i<\ell$, $G$ has an edge $\\{v_{i},v_{i+1}\\}$ and $v_{i}$ and $v_{j}$
are distinct for any $1\leq i<j\leq\ell$. Vertices $v_{1}$ and $v_{\ell}$ is
_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. 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. A sequence $C\coloneqq(v_{1},\ldots,v_{\ell},v_{1})$ is a _cycle_ if the
sequence $(v_{1},\ldots,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\coloneqq\\{\\{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\coloneqq\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 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

Since there exist several different techniques for designing efficient
enumeration algorithms, we briefly explain in this section the ones used in
this paper.

_Binary Partition_ (also _branching_ or _flashlight_ approach), is a basic
technique that recursively splits the space of solutions $\mathcal{S}$ into
two sets $\mathcal{S}^{\prime}$ and $\mathcal{S}^{\prime\prime}$ such that
$\mathcal{S}=\mathcal{S}^{\prime}\cup\mathcal{S}^{\prime\prime}$. We
illustrate the technique with a useful example about enumerating all
$k$-graphlets in a graph $G=(V,E)$. We first pick a vertex $v\in V$ and we
partition $\mathcal{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
$\mathcal{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)\in\mathcal{E}$. The set of all children of
$X$ is called $ch(X)$. A key factor when designing an efficient enumeration
algorithm based on this technique, is to ensure that each internal node in
$\mathcal{T}$ has at least two children. Suppose that any internal node
$X\in\mathcal{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_{X\in\mathcal{T}}T(X))$.
Notice that if there exists an internal node with exactly one child in
$\mathcal{T}$, the amortized time complexity of the algorithm worsens to
$O(d\cdot\max_{X\in\mathcal{T}}T(X))$, where $d$ is the depth of
$\mathcal{T}$.

This technique has been widely used in the literature for the enumeration of
structures 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, 35, 36, 37, 38, 39, 40]. In this
paper, we will use this strategy for designing the algorithm of Section 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 [40, 19].

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_.

######  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)\quad\geq\quad\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 Section 4 is designed according to the
push-out amortization strategy.

##  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)$, $\mathit{In}$ and
$\mathit{Ex}$ be two disjoint vertex sets, and
$\mathcal{S}(G,\mathit{In},\mathit{Ex},k)$ be the set of all $k$-graphlets of
$G$ that contain all and only the vertices in the set $\mathit{In}$, and do
not contain any vertex in $\mathit{Ex}$. For brevity, when $G$ is clear from
the context, we denote this set as $\mathcal{S}(\mathit{In},\mathit{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\mathit{In}$. The basic
strategy consists of partitioning the set
$\mathcal{S}(\mathit{In},\mathit{Ex},k)$ into two sets
$\mathcal{S}(\mathit{In}\cup\\{v\\},\mathit{Ex},k)$ and
$\mathcal{S}(\mathit{In},\mathit{Ex}\cup\\{v\\},k)$, given a vertex $v\in
N(\mathit{In})\setminus\mathit{Ex}$. Then, we check if these sets contain at
least one solution by choosing an arbitrary vertex from $\mathit{In}$, running
a graph traversal from it, excluding vertices in $\mathit{Ex}$, and checking
if we reach $k-\left|\mathit{In}\right|$ vertices to be added to
$\mathit{In}$. This strategy ensures that $G[\mathit{In}]$ is connected, as it
is connected at first (initially $\mathit{In}=\\{r\\}$) and we add neighbors
of $\mathit{In}$ at each step.

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

######  Observation 1.

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

####  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 above simple binary partition algorithm runs
in amortized $O(nm)$ time, since each recursive call takes $O(m)$ time and the
depth of $\mathcal{T}$ is at most $n$. In this approach, the number of tree
nodes in $\mathcal{T}$ is $O(nN)$, where $N$ is the number of leaves, that is,
the number of $k$-graphlets. Therefore, the amortized time complexity is
$O(nm)$. To improve this time complexity, we first reduce the number of nodes
in $\mathcal{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
$\mathcal{S}(\mathit{In},\mathit{Ex}\cup\\{v\\},k)$ has no solution.

A vertex $v$ is _mandatory_ for $G$, $\mathit{In}$ and $k$ if the connected
component in $G-v$ that contains the vertices in $\mathit{In}$ has at most
$k-1$ vertices. Notice that a vertex $v$ is mandatory if and only if
$\mathcal{S}(G,\mathit{In},k)=\mathcal{S}(G,\mathit{In}\cup\\{v\\},k)$. In
addition, a mandatory vertex is an articulation point if the connected
component in $G$ that contains $\mathit{In}$ has at least $k+1$ vertices. In
our partitioning strategy, the basic operation is to determine if
$\mathcal{S}(G,\mathit{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 $\mathit{In}$ a set of vertices
such that $G[\mathit{In}]$ is connected. We can determine if
$\mathcal{S}(G,\mathit{In},k)$ is empty or not in
$O(\min\\{m,k^{2},k\Delta\\})$ 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
$\mathit{In}$ has at least $k$ vertices, $\mathcal{S}(G,\mathit{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\in F$ connects vertices in
$U$. Therefore, $\left|F\right|$ is bounded by $\min\\{k^{2},k\Delta\\}$ and
the breadth-first search terminates in $O(\min\\{m,k^{2},k\Delta\\})$ 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.

Input: A graph $G$, a set of vertices $\mathit{In}$, an integer $k$

Output: All $k$-graphlets that contain $\mathit{In}$ in $G$

1

2Function  _LIN-ENUM-V(_$G$ , $\mathit{In}$, $k$_)_

3 if  _$\left|\mathit{In}\right|=k$_ then output $\mathit{In}$ and return

4 while  _$N(\mathit{In})$ has a mandatory vertex $u$_ do

5 $\mathit{In}\leftarrow\mathit{In}\cup\\{u\\}$

6 if  _$\left|\mathit{In}\right|=k$_ then Output $\mathit{In}$ and return

7

Let $v$ be a vertex in $N(\mathit{In})$

// $v$ is non-mandatory

8 LIN-ENUM-V(_$G,\mathit{In}\cup\\{v\\},\emptyset,k$_)

9 LIN-ENUM-V(_$G-v,\mathit{In},k$_)

10

Algorithm 1 An amortized $O(m)$-time algorithm for $k$-graphlet enumeration

######  Theorem 2.

Algorithm 1 enumerates all $k$-graphlets in $G$ that contain $\mathit{In}$.

###### Proof.

Let $X$ be a node in $\mathcal{T}$, $G_{X}$ be the input graph of the call
$X$, $\mathit{In}_{X}$ be a set of vertices such that $G_{X}[\mathit{In}_{X}]$
is connected.We show that each node in $\mathcal{T}$ partitions
$\mathcal{S}(G_{X},\mathit{In}_{X},k)$ into two non-empty sets
$\mathcal{S}(G_{X},\mathit{In}_{X}\cup\\{v\\},k)$ and
$\mathcal{S}(G_{X}-v,\mathit{In},k)$. By definition, adding mandatory vertices
in $\mathit{In}_{X}$ does not change the set of $k$-graphlets. Moreover, since
we add mandatory vertices that are adjacent to a vertex in $\mathit{In}_{X}$,
we do not break the connectivity of $G_{X}[\mathit{In}_{X}]$. Let $S$ be a
$k$-graphlet in $\mathcal{S}(G_{X},\mathit{In}_{X},k)$: if $S$ contains $v$,
$S\in\mathcal{S}(G_{X},\mathit{In}_{X}\cup\\{v\\},k)$, otherwise
$S\in\mathcal{S}(G_{X}-v,\mathit{In}_{X},k)$. From the definition of
$\mathcal{S}(G_{X},\mathit{In}_{X},k)$,
$\mathcal{S}(G_{X},\mathit{In}_{X}\cup\\{v\\},k)$ and
$\mathcal{S}(G_{X}-v,\mathit{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 $\mathit{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 [41, 42]. 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 1 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
$\mathit{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 [42]: 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(\mathit{In})$ has at most
two mandatory vertices when $G$ is sufficiently large.

Input: A graph $G$, an integer $k$, and a set of vertices $\mathit{In}$

Output: All $k$-graphlets of $G$ that contain $\mathit{In}$

1

2Function  _ENUM-V(_$G$ ,$\mathit{In}$,$k$_)_

3 if  _$\left|\mathit{In}\right|=k-1$_ then

4 for  _$u\in N(\mathit{In})$_ do output $\mathit{In}\cup\\{u\\}$

5 return

6

7 while  _$\left|N(\mathit{In})\right|=1$_ do // Follow the chain

8 Let $v$ be the vertex in $N(\mathit{In})$

9 $\mathit{In}\leftarrow\mathit{In}\cup\\{v\\}$

10 if  _$\left|\mathit{In}\right|=k-1$_ then

11 for  _$u\in N(\mathit{In})$_ do output $\mathit{In}\cup\\{u\\}$

12 return

13

14

15 Let $x,y$ be two distinct vertices in $N(\mathit{In})$

16 if  _either $x$ or $y$ is non-mandatory for $G,\mathit{In},k$_ then

17 Let $z$ be a non-mandatory vertex in $\\{x,y\\}$

18 ENUM-V(_$G,\mathit{In}\cup\\{z\\},k$_)

19 ENUM-V(_$G-z,\mathit{In},k$_)

20

21 else // $|V|<2k$ by Lemma 3

22 LIN-ENUM-V(_$G,\mathit{In},k$_)

23

24

Algorithm 2 An amortized $O(k^{2})$-time $k$-graphlet enumeration algorithm.

######  Lemma 3.

Let $U$ be a set of vertices such that $G[U]$ is connected, $x,y\in N(U)$. If
$x,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$. Let $T_{C}$ be a biconnected-component tree of $G$. We denote the
connected component in $G-x$ that contains the vertices in $U$ as
$T_{C}(x,U,1)$ and the other connected components in $G-x$ as $T_{C}(x,U,0)$.
Since both $x$ and $y$ are mandatory, both $T_{C}(x,U,1)$ and $T_{C}(y,U,1)$
have at most $k-1$ vertices. Moreover, any vertex in $G$ is contained either
in $T_{C}(x,U,1)$ or $T_{C}(y,U,1)$. Therefore, the number of vertices of $G$
is at most $\left|V(T_{C}(x,U,1))\right|+\left|V(T_{C}(y,U,1))\right|\leq
2k-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.

######  Theorem 4.

Algorithm 2 runs in $O(m+N\cdot k^{2})$ time and $O(n+m)$ space, where $N$ is
the number of $k$-graphlets that contain $r\in\mathit{In}$.

###### Proof.

We analyze the time complexity of each node $X\in\mathcal{T}$, and we denote
by $G_{X}$ the input graph of the call $X$, with the corresponding set
$\mathit{In}_{X}$. Notice that $k$ is the same for all instances in
$\mathcal{T}$. We first analyze the time complexity when
$\left|\mathit{In}_{X}\right|=k-1$ (trivially, there cannot be a node
satisfying $\left|\mathit{In}_{X}\right|=k$). In this case, we can enumerate
all $k$-graphlets in $O(k^{2}+k\cdot N_{X})$ time, where
$N_{X}=\left|\mathcal{S}(G_{X},\mathit{In}_{X},k)\right|$. For each $u\in
N_{G_{X}}(\mathit{In})$, $\mathit{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 $\left|\mathit{In}_{X}\right|<k-1$. When
$N_{G_{X}}(\mathit{In}_{X})$ has only one vertex, we can find such vertex in
$O(k^{2})$ time, and it is easy to compute all such vertices in the same time
complexity. Thus, in what follows we assume that $N_{G_{X}}(\mathit{In}_{X})$
contains at least two vertices. Let $x$ and $y$ be two distinct vertices in
$N_{G_{X}}(\mathit{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)\geq 3k$, we consider the following
amortized analysis: let $Y$ be a node generated by $G_{X}$ and
$\mathit{In}_{X}\cup\\{z\\}$. We call _left child_ a child of a recursive node
generated by adding one vertex to $\mathit{In}$ (i.e., in line 2), whereas we
call _right child_ a child of a recursive node generated by removing a vertex
from $G$ (i.e., in line 2). For a node $Z\in\mathcal{T}$, we call a path
$\mathcal{P}$ from $Z$ to a leaf in $\mathcal{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)\geq 3k$ and $\left|\mathit{In}_{X}\right|<k-1$,
$N_{G_{X}}(\mathit{In}_{X}\cup\\{z\\})$ has at least
$d_{G_{X}}(z)-\left|\mathit{In}_{X}\right|\geq 2k+2$ vertices. Notice that,
for a node $Z$, if $N_{G_{Z}}(\mathit{In}_{Z})$ has
$k-\left|\mathit{In}_{Z}\right|$ vertices, there is no mandatory vertex.
Therefore, by picking a vertex $u\in N_{G_{X}}(\mathit{In}\cup\\{z\\})$ and
removing $u$ $k$ times, we cannot create new mandatory vertices; this means
that the right path of $Y$ has at least $d_{G_{X}}(z)-2k\geq 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(m+N\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
$\mathit{In}_{X}$ and $\mathit{In}_{Y}$ and $G_{X}$ and $G_{Y}$. It is clear
that the sum of the difference between $\mathit{In}_{X}$ and $\mathit{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)$. ∎

Figure 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.

####  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 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(m+N\cdot k\cdot\min\\{k,\Delta\\})$ time, where $N$ is
the number of $k$-graphlets in $G$ that contain $r\in\mathit{In}$. Thus, if
$\Delta=O(1)$, Algorithm 2 runs in $O(m+k\cdot N)$ time.

###### Proof.

The bottleneck of Algorithm 2 is the deletion of a vertex, that can be
trivially done in $O(\Delta)$ time. Therefore, each recursive call can be
performed in $O(k\cdot\min\\{k,\Delta\\})$ time and the statement holds. ∎

###  3.2 Generating instances for Algorithm 2

Algorithm 2 enumerates all $k$-graphlets in $G$ that contain a specific set of
vertices $\mathit{In}$, in $O(k^{2})$ 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, and we prove the overall complexity for $k$-graphlet enumeration.

######  Theorem 6.

Let $G=(V,E)$ be a graph and $k\in\mathbb{N}$. 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. For each $i$, we enumerate
$\mathcal{S}(G_{i}=G-\\{v_{1},\ldots,v_{i-1}\\},\\{v_{i}\\},k)$. Let $C_{i}$
be the connected component that contains $v_{i}$ in $G_{i}$. We can determine
if $\mathcal{S}(G_{i},\\{v_{i}\\},k)$ is empty or not in
$O(\min\\{\left|E(C_{i})\right|,k^{2}\\})$ time using Lemma 2. If
$\mathcal{S}(G_{i},\\{v_{i}\\},k)$ contains at least a solution, we can
enumerate all solutions in $O(k^{2}\cdot N_{i})$ time, where $N_{i}$ is the
number of solutions in $\mathcal{S}(G_{i},\\{v_{i}\\},k)$. Since each
recursive call of Algorithm 2 can be performed in $O(k^{2})$ time, the running
time can be bounded in $O(k^{2}\cdot N_{i})$ time. Moreover, the number of $i$
that satisfies $\mathcal{S}(G_{i},\\{v_{i}\\},k)\neq\emptyset$ is at most $N$,
the total time complexity of Algorithm 2 is $O(k^{2}\cdot N)$.

We finally analyze the time complexity of the instances generation, that is,
the time complexity of Algorithm 3. We consider two cases. The first case is
$\mathcal{S}(G_{i},\\{v_{i}\\},k)$ has at least one solution. This case does
not worsen the time complexity since it can be done in $O(k^{2})$ time.
Otherwise, $\mathcal{S}(G_{i},\\{v_{i}\\},k)$ contains no solutions, and we
take $O(k^{2})$ time to recognize it. However, in this case, we can determine
that one connected component $C$ in $G-\\{v_{1},\ldots,v_{i-1}\\}$ has at most
$k-1$ vertices. Moreover, for a vertex $v_{j}\in C$, we determine that there
are $k$-graphlets that contain $v_{j}$ in $G_{j}$ in constant time. Therefore,
the total time complexity is $O(n+m+k^{2}\cdot N)$. The space consumption of
the whole strategy is $O(n+m)$, needed by Algorithm 2, as Algorithm 3 uses
asymptotically less space. ∎

Input: A graph $G=(V,E)$, a non-negative integer $k$

Output: $I\subseteq\\{1,\ldots,n\\}$ such that, for each $i\in I$,
$G-\\{v_{1},\ldots,v_{i-1}\\}$ has at least one $k$-graphlet containing
$v_{i}$

1 Function  _Gen-Ins(_$G=(V,E),k$_)_

2 Let $r_{1},\ldots,r_{n}$ be $n$ binary variables initialized to $0$

3 $G_{0}\leftarrow G$

4 for  _$1\leq i\leq n$_ do

5 $C_{i-1}\leftarrow$ a connected component in $G_{i-1}$ containing $v_{i}$

6 if  _$r_{i}=0$_ then

7 if  _$\left|V(C_{i-1})\right|\geq k$_ then output $i$

8

9 else

10 if  _$\left|V(C_{i-1})\right| <k$_ then

11 for  _$v_{j}\in V(C_{i-1})$_ do $r_{j}\leftarrow 1$

12

13

14 $G_{i}\leftarrow G_{i-1}-\\{v_{i}\\}$

15

16

17

18for  _ $i\in$ Gen-Ins(_G, k_)_ do // Main enumeration loop

19 ENUM-V(_$G_{i-1}$ ,$\\{v_{i}\\}$,$k$_)

Algorithm 3 Generating instances for Algorithm 2.

##  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 Section 3 by replacing $G$ with its line
graph (which represents the adjacency between the edges of $G$ rather than
between its nodes). This gives an amortized $O(k^{2})$-time algorithm for
enumerating all edge $k$-graphlets, but we achieve a better complexity, 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.

###  4.1 Trimming operation

In the following, given a graph $G=(V,E)$ and two disjoint sets
$\mathit{In},\mathit{Ex}\subseteq E$ of its edges, such that $G[\mathit{In}]$
is connected, we denote by $\mathcal{S}(G,\mathit{In},\mathit{Ex},k)$ the set
of edge $k$-graphlets that contain $\mathit{In}$ and do not contain
$\mathit{Ex}$. We denote by $V_{\mathit{In}}$ the set of vertices
$V(G[\mathit{In}])$.

As
$\mathcal{S}(G,\mathit{In},\mathit{Ex},k)=\mathcal{S}(G-\mathit{Ex},\mathit{In},\emptyset,k)$,
we can simply ignore $\mathit{Ex}$ and take the reduced graph $G$ after the
preliminary removal of $\mathit{Ex}$. We also remove _unnecessary_ edges,
whose distance from $V_{\mathit{In}}$ is at least $k-\left|\mathit{In}\right|$
(and thus cannot be part of solutions containing $\mathit{In}$). The removal
of both $\mathit{Ex}$ and the unnecessary edges from $G$ is called _trimming
operation_ , and is denoted by trim($G,\mathit{In},\mathit{Ex},k$).

######  Lemma 4.

Let $H$ be the graph obtained by trim($G,\mathit{In},\mathit{Ex},k$). We can
perform the trimming operation in $O(\left|Ex\right|+\left|E(H)\right|)$ time.

###### Proof.

We first remove the edges in $\mathit{Ex}$ from $G$ in
$O(\left|\mathit{Ex}\right|)$ time. We can obtain the desired graph $H$ by
removing all unnecessary edges from $G-\mathit{Ex}$. It can be done in
$O(\left|\mathit{Ex}\right|+\left|E(H)\right|)$ time using a breadth-first
search. We first traverse the edges in $G[\mathit{In}]$ and contract all edges
in $\mathit{In}$. Let $v$ be the vertex obtained by contracting edges
$\mathit{In}$. By collecting all edges with the distance from $v$ at most
$k-\left|\mathit{In}\right|$, we can construct $H$ in
$O(\left|Ex\right|+\left|E(H)\right|)$ time. ∎

We remark that the trimming operation is crucial to get our time bounds using
push-out amortization. Moreover, the operation is safe with respect to
_mandatory_ edges: an edge $e$ is mandatory if the connected component in
$G-e$ containing $V_{\mathit{In}}$ has less than $k$ edges (hence, $e$ should
be included in all solutions containing $G[\mathit{In}]$). Since an
unnecessary edge cannot be mandatory, we do not lose solutions after trimming
$G$.

For this reason, in the rest of this section we focus on the problem of
enumerating the edges $k$-graphlets of a generic instance
$\mathcal{S}(G,\mathit{In},k)$, forgetting about $\mathit{Ex}$ and unnecessary
edges. We say that an instance is _trimmed_ if it has no unnecessary edges and
$\mathit{Ex}=\emptyset$.

###  4.2 Partition strategy

We partition $\mathcal{S}(G,\mathit{In},k)$ into two disjoint sets, which are
enumerated separately:

  * •

$\mathcal{S}_{\tt far}(G,\mathit{In},k)$ is the set of solutions in
$\mathcal{S}(G,\mathit{In},k)$ that contain an edge $e$ satisfying
$dist(V_{\mathit{In}},e)=k$.

  * •

$\mathcal{S}_{\tt near}(G,\mathit{In},k)$ is
$\mathcal{S}(G,\mathit{In},k)\setminus\mathcal{S}_{\tt far}(G,\mathit{In},k)$.

######  Observation 5.

Let $H$ be an edge $k$-graphlet in $\mathcal{S}_{\tt far}(G,\mathit{In},k)$.
Then $H-e$ must be a shortest path between $V_{\mathit{In}}$ and an endpoint
of $e$.

From 5, we can enumerate all edge $k$-graphlets in $\mathcal{S}_{\tt
far}(\mathit{In},k,r)$ 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 [43, Section 4.1]).

Based on this, we focus on the enumeration of $\mathcal{S}_{\tt
near}(\mathit{In},k,r)$, and denote the set of edges $\\{e\in E\mid
dist(V_{\mathit{In}},e)=k\\}$ as $E_{\tt far}$, calling them far edges.

######  Lemma 6.

$\mathcal{S}_{\tt near}(G,\mathit{In},k)=\mathcal{S}(G-E_{\tt
far},\mathit{In},k)$.

###### Proof.

For any $H\in\mathcal{S}_{\tt near}(G,\mathit{In},k)$, $H$ cannot be in
$\mathcal{S}_{\tt far}(G,\mathit{In},k)$ as it does not contain any edge from
$E_{\tt far}$; hence, $H\in\mathcal{S}(G-E_{\tt far},\mathit{In},k)$. Vice
versa, for any $H\in\mathcal{S}(G-E_{\tt far},\mathit{In},k)$, $H$ is
contained in $\mathcal{S}_{\tt near}(G,\mathit{In},k)$ by definition. ∎

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

Algorithm 4 summarizes the partition strategy, where we organize the
computation so that the push-out amortization can be applied. Specifically, we
say that an edge $e$ is _heavy_ if the number of far edges in $G-e$ is more
than $(\left|E\right|-1)/10$. Moreover, we assume that the trim() function
returns, in this order, the trimmed graph $H$, the set $\mathit{In}$ adjusted
accordingly, and the value of $k$, for compatbility with the Enum-E(__)
function.

######  Lemma 7.

For a trimmed instance, $\Gamma(V_{\mathit{In}})$ has at most one heavy edge.

###### Proof.

Suppose that $\Gamma(V_{\mathit{In}})$ has two heavy edges $e\neq f$. In what
follows, we denote $G-\\{e\\}$ as $G_{e}$ and $G-\\{f\\}$ as $G_{f}$. Let $g$
be an edge in $E$ not contained in both $G_{e}$ and $G_{f}$. Since $g$ is not
unnecessary in $G$ and the distance between $g$ and $r$ in $G_{e}$ is at least
$k$, all shortest paths between $V_{\mathit{In}}$ and $g$ contain $e$. By a
similar argument, all shortest paths between $r$ and $g$ in $G$ contain $f$.
However, this does not occur since $e$ and $f$ share $V_{\mathit{In}}$.
Therefore, an edge in $E$ contains either $G_{e}$ or $G_{f}$ and $E\setminus
E(G_{e})$ and $E\setminus E(G_{f})$ are disjoint. However,
$\left|E(G_{e})\right|+\left|E(G_{f})\right|$ exceeds $\left|E\right|$, which
is a contradiction, and $\Gamma(V_{\mathit{In}})$ has at most one heavy edge.
∎

We obtain the following bound on space.

######  Theorem 7.

Algorithm 4 correctly outputs $\mathcal{S}(G,\mathit{In},k)$ using $O(n+m)$
space.

###### Proof.

By 5 and Lemma 6, we can enumerate all solutions in $\mathcal{S}_{\tt
far}(G,\mathit{In},k)$ and $\mathcal{S}_{\tt
near}(G,\mathit{In},k)=\mathcal{S}(G-E_{\tt far},\mathit{In},k)$. By Lemma 7,
$\Gamma(V_{\mathit{In}})$ contains at least one non-heavy edge $e$. Moreover,
when $\Gamma(V_{\mathit{In}})$ has only one edge, we add this edge to
$\mathit{In}$ until $\Gamma(V_{\mathit{In}})$ has at least two edges since it
is mandatory. Thus, we can partition $\mathcal{S}(G-E_{\tt far},k,r)$ into two
sets using a non-heavy edge. In each node, we can partition
$\mathcal{S}(G,\mathit{In},k)$ and Algorithm 4 correctly enumerates all edge
$k$-graphlets that contain $\mathit{In}$. Moreover, in each node, we store
only the set of edges added to $\mathit{In}$ and the set of removed edges.
Therefore, the total space is $O(n+m)$ at any time. ∎

Input: Graph $G=(V,E)$, edge set $\mathit{In}\subseteq E$, non-negative
integer $k$

Output: All edge $k$-graphlets of $G$ that contains $\mathit{In}$

1 Function  _Enum-E(_$G=(V,E),\mathit{In},k$_)_

2 if  _$\left|\mathit{In}\right|=k$_ then Output $\mathit{In}$ and return

3 Enumerate all solutions that contain a far edge.

4 while  _$\Gamma(V_{\mathit{In}})$ contains a mandatory edge_ do

5 Let $e$ be a mandatory edge in $\Gamma(V_{\mathit{In}})$

6 $\mathit{In}\leftarrow\mathit{In}\cup\\{e\\}$

7 if  _$\left|\mathit{In}\right|=k-1$_ then

8 for  _$f\in\Gamma(V_{\mathit{In}})$_ do output $\mathit{In}\cup\\{f\\}$;
return

9

10

11

12 Let $e$ be a non-heavy edge in $\Gamma_{G-E_{\tt far}}(V_{\mathit{In}})$

13 Enum-E(_trim( $G-E_{\tt far},\\{e\\},\emptyset,k$)_)

14 Enum-E(_trim( $G-E_{\tt far},\emptyset,\\{e\\},k$)_)

15

Algorithm 4 Given a graph $G$, a set $\mathit{In}$ of its edges inducing a
connected subgraph, and a non-negative integer $k$, the algorithm enumerates
all edge $k$-graphlets that contain $\mathit{In}$.

###  4.3 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 our algorithm runs in
$O(k\cdot N)$ time if the instance received at the root is already trimmed. It
is not difficult to show that our algorithm runs in amortized $O(m)$ time
since the trimming operation, algorithm 4, and mandatory edges enumeration
runs in amortized $O(m+\left|ch(X)\right|)$ time, where $m$ is the number of
edges in the graph received at the root, and $X$ is an internal node. Since
the sum of the number of children is bounded by the number of nodes in a
rooted tree, the amortized time complexity of our proposed algorithm is
$O(m)$.

Our goal is to 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. In each
internal node $X$, we can be done in $O(m_{X}+\left|ch(X)\right|)$ time
without two recursive calls since Algorithm 4 can be done in
$O(m_{X}+\left|ch(X)\right|)$ time, where $G_{X}$ is the input graph of $X$
and $m_{X}$ is the number of edges in $G_{X}$. We can compute the trimming
operation in linear time from Lemma 4. Therefore, the total running time in
$X$ is $O(m_{X}+\left|ch(X)\right|)$ time.

We show that each node $X$ satisfies the PO condition by setting $\alpha=5/4$
and $\beta=3$, where $c^{*}$ is an arbitrary constant that is larger than the
constant hidden in the big-Oh notation for computation time at internal nodes
and at leaf nodes. To simplify the analysis, we assume that each internal node
$X$ takes $c^{*}(m_{X}+\left|ch(X)\right|)$ time and each leaf node $T$ takes
$c^{*}\cdot k$ time.

When $m_{X}\leq 4k$, Algorithm 4 runs in amortized $O(k)$ time since it
achieves amortized $O(m_{X})$ time. In what follows, we analyze the case such
that $m_{X}>4k$. We give the lower bound of the size of each trimmed instance
received by a child. We first show that adding one edge to $\mathit{In}$ does
not change the size of a graph when an instance is trimmed.

######  Lemma 8.

Suppose that $E_{\tt far}=\emptyset$ in the instance $G,\mathit{In},k$. Then,
the graph obtained by trim($G,\\{e\\},\emptyset,k$) has $\left|E(G)\right|$
edges.

###### Proof.

From the definition of the operation trim(), we remove all unnecessary edges.
For an edge $f\in E(G)$, the distance from $V_{\mathit{In}}$ to $f$ does not
change. Thus, this instance $G,\mathit{In},k$ has no unnecessary edges. ∎

We next consider how much the trimming operation reduces the size of a graph,
and the following corollaries are immediate.

######  Corollary 9.

The graph obtained by trim($G,\emptyset,E_{\tt far},k$) has at least
$\left|E(G)\right|-\left|E_{\tt far}\right|$ edges.

###### Proof.

Follows from a similar argument to Lemma 8. ∎

######  Corollary 10.

Suppose that $E_{\tt far}=\emptyset$ and $e$ is a non-heavy edge in
$\Gamma(V_{\mathit{In}})$. Then, the graph obtained by
trim($G,\emptyset,\\{e\\},k$) has at least $9\left|E(G)\right|/10-1$ edges.

###### Proof.

First, we observe that this trimming operation only removes the edge $e$ as
$E_{far}=\emptyset$ and does not create any unnecessary edge, as $e$ is in
$\Gamma(V_{\mathit{In}})$ and $e$ is not mandatory by construction in
Algorithm 4. Since $e$ is non-heavy, we may generate at most
$(\left|E(G)\right|-1)/10$ far edges, which will lead to a trimmed graph
$G^{\prime}$ with
$\left|E(G^{\prime})\right|\geq\left|E(G)\right|-(\left|E(G)\right|-1)/10-1=9(\left|E(G)\right|-1)/10\geq
9\left|E(G)\right|/10-1$. ∎

Now, we are ready to give our analysis.

######  Lemma 11.

Let $X$ be a node in the recursion tree of Algorithm 4. Moreover, let
$(G_{X},\mathit{In}_{X},k_{X})$ be an instance corresponding to $X$. Suppose
that $G_{X}$ has at least $4k$ edges. Then, $X$ satisfies the PO condition by
setting $\alpha=5/4$ and $\beta=3$.

###### Proof.

When $\left|E_{X}\right|\leq 4k$, the PO condition holds by setting $\beta$
greater than $3$. Therefore, suppose that $\left|E_{X}\right|>4k$. Let $F_{X}$
be the set of far edges in $G_{X}$. Since the number of children of $X$ is at
least $\left|F_{X}\right|$, the graph obtained by trim($G,\emptyset,F_{X},k$)
has at least $\left|E_{X}\right|-\left|F_{X}\right|$ edges by Corollary 9.
From Lemmas 8 and 10, a lower bound of the sum of the number of edges in two
children is as follows.

$\displaystyle\sum_{Y\in ch(X)}T(Y)$
$\displaystyle=c^{*}(\left|E_{X}\right|-\left|F_{X}\right|)+9c^{*}(\left|E_{X}\right|-\left|F_{X}\right|)/10-1+c^{*}\cdot\left|F_{X}\right|$
$\displaystyle\geq
19c^{*}\left|E_{X}\right|/10-9c^{*}\left|F_{X}\right|/10-2c^{*}$

We next analyze the term $\alpha T(X)-\beta(\left|ch(X)\right|+1)T^{*}$ as
follows.

$\displaystyle\alpha T(X)-\beta(\left|ch(X)\right|+1)T^{*}$
$\displaystyle=5c^{*}\left|E_{X}\right|/4-3c^{*}\cdot\left|F_{X}\right|$

Therefore,

$\displaystyle\sum_{Y\in ch(X)}T(Y)-\alpha
T(X)+\beta(\left|ch(X)\right|+1)T^{*}\geq
13c^{*}\left|E_{X}\right|/20+21c^{*}\left|F_{X}\right|/10-2c^{*}$

Since $\left|E_{X}\right|>4k$, that is, $\left|E_{X}\right|\geq 9$, the PO
condition holds. ∎

Therefore, each internal node with a large enough graph satisfies the PO
condition and we obtain the following corollary.

######  Theorem 8.

Algorithm 4 runs in total $O(n+m+k\cdot N)$ time and $O(n+m)$ space, 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.4 Generating instances for Algorithm 4

Finally, we show that the trimmed instance can be generated in $O(n+m+k\cdot
N)$ time. To this end, we show our instance generation algorithm in Algorithm
5. By combining Algorithms 4 and 5, we obtain the following theorem.

######  Theorem 9.

Let $G$ be a graph and $k$ be an integer. Then, 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.

We show that we can enumerate all edge $k$-graphlets using Algorithm 4 as a
subroutine. Let the vertices of $G$ be numbered as $v_{1},\ldots,v_{n}$. For
each $i$, we enumerate
$\mathcal{S}(G_{i}=G-\\{v_{1},\ldots,v_{i-1}\\},\emptyset,k)$. Let $C_{i}$ be
the connected component that contains $v_{i}$ in $G_{i}$. We can determine
that $\mathcal{S}(G_{i},\emptyset,k)$ is empty or not in
$O(\min\\{k,\left|E(C_{i})\right|\\})$ time. If
$\mathcal{S}(G_{i},\emptyset,k)$ has a solution, we can obtain an trimmed
instance trim($G_{i},\emptyset,k$) in time $O(\left|E(H_{i})\right|)$ by Lemma
4, where $H_{i}$ is the output of the trimming operation. In this case, we can
enumerate $\mathcal{S}(G_{i},\emptyset,k)$ in $O(k\cdot N)$ time since we have
the trimmed instance $H_{i}$. Moreover, the number of $i$’s that satisfies
$\mathcal{S}(G_{i},\emptyset,k)\neq\emptyset$ is at most $N$, so the total
time complexity to generate such instances is $O(k\cdot N)$.

Finally, we consider the time complexity of generating empty instances. When
$\mathcal{S}(G_{i},\emptyset,k)$ is empty, the number of edges in $C_{i}$ is
less than $k$. For $v_{j}\in\\{v_{i+1},\ldots,v_{n}\\}\cap V(C_{i})$, we
determine $\mathcal{S}(G_{j},\emptyset,k)$ has no solutions in constant time.
We consider the set of vertices $U_{i}\subseteq\\{v_{i},\ldots,v_{n}\\}$ such
that $\mathcal{S}(G_{i},\emptyset,k)$ is empty. We first show that each
connected component in $G[U_{i}]$ has at most $k-1$ edges. Suppose that
$G[U_{i}]$ has a connected component $C$ that has at least $k$ edges. Let
$v_{j}$ be the vertex in $C$ with the minimum index. It contradicts that
$\mathcal{S}(G_{j},\emptyset,k)$ is empty since $G_{j}$ contains $C$. Finally,
in our instance generation algorithm, a vertex $u$ is marked at most once.
When we search $\Gamma(u)$, this cost does not worsen the time complexity
since there is at least one solution. The other case happens only once, and we
can generate all instances in $O(n+m+k\cdot N)$ time. ∎

Input: A graph $G=(V,E)$, an non-negative integer $k$

Output: For each $1\leq i\leq n$, output
trim($G-\\{v_{1},\ldots,v_{i-1}\\},\emptyset,\emptyset,k$)

1 Function  _Gen-Ins(_$G=(V,E),k$_)_

2 Let $r_{1},\ldots,r_{n}$ are $n$ binary variables initialized by $0$.

3 $G_{0}\leftarrow G$

4 for  _$1\leq i\leq n$_ do

5 $C_{i-1}\leftarrow$ a connected component in $G_{i-1}$ that containing
$v_{i-1}$

6 if  _$r_{i}=0$_ then

7 if  _$\left|E(C_{i-1})\right|\geq k$_ then output $i-1$

8

9 else

10 if  _$\left|E(C_{i-1})\right| <k$_ then

11 for  _$v_{j}\in V(C_{i-1})$_ do $r_{j}\leftarrow 1$

12

13

14 $G_{i}\leftarrow G_{i-1}-\\{v_{i}\\}$

15

16

17

18for  _ $j\in$ Gen-Ins(_G, k_)_ do // Main enumeration loop

19 Enum-E(_trim( $G_{j},\emptyset,\emptyset,k$)_)

Algorithm 5 An algorithm for generating instances for Algorithm 4.

###  4.5 Modification for the $k$-subtrees enumeration

We propose an algorithm for enumerating all $k$-subtrees with small
modifications of Algorithm 4. Let $X$ be a node and $G_{X}$ be a graph,
$\mathit{In}_{X}$ be a set of edges, $k$ be an integer. The partition strategy
is completely the same Algorithm 4. For an edge
$e=\\{u,v\\}\in\Gamma_{G_{X}}(\mathit{In}_{X})$ such that $u$ is contained in
$\mathit{In}_{X}$, an edge that connects vertices $v$ and a vertex
$G_{X}[\mathit{In}_{X}]$ cannot be added to $\mathit{In}_{X}\cup\\{e\\}$.
Thus, we remove such edges from $G_{X}$. However, there are $k$-subtrees that
contain such edges. The only difference between our $k$-subtree enumeration
algorithm and our edge $k$-graphlet enumeration algorithm is the difference in
the definition of the partition strategy. The correctness of our algorithm can
be shown from the same arguments as for our edge $k$-graphlet enumeration
algorithm. Moreover, the PO condition clearly holds. When we add an edge
$e=\\{u,v\\}$ to $\mathit{In}_{X}$ and many edges that connects $v$ and a
vertex in $G_{X}[\mathit{In}_{X}]$ exists between $u$ and $v$, we can generate
all subproblems in linear time. Therefore, we obtain an algorithm for
enumerating all $k$-subtrees that runs the same time complexity with a small
modification of Algorithm 4.

######  Theorem 10.

Let $G$ be a graph and $k$ be an integer. Then, we can enumerate all
$k$-subtrees in $O(n+m+k\cdot N)$ time and $O(n+m)$ space, where $N$ is the
number of solutions.

##  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, 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.

## References

  *   * Lacroix et al. [2006] Lacroix, V., Fernandes, C.G., Sagot, M.-F.: Motif search in graphs: application to metabolic networks. IEEE/ACM transactions on computational biology and bioinformatics 3(4), 360–368 (2006)
  * Ciriello and Guerra [2008] Ciriello, G., Guerra, C.: A review on models and algorithms for motif discovery in protein–protein interaction networks. Briefings in Functional Genomics 7(2), 147–156 (2008) https://doi.org/10.1093/bfgp/eln015 https://academic.oup.com/bfg/article-pdf/7/2/147/655985/eln015.pdf
  * Yu et al. [2020] Yu, S., Feng, Y., Zhang, D., Bedru, H.D., Xu, B., Xia, F.: Motif discovery in networks: A survey. Computer Science Review 37, 100267 (2020)
  * Fortunato [2010] Fortunato, S.: Community detection in graphs. Physics Reports 486(3), 75–174 (2010) https://doi.org/10.1016/j.physrep.2009.11.002
  * Pržulj et al. [2004] 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 https://academic.oup.com/bioinformatics/article-pdf/20/18/3508/48906619/bioinformatics_20_18_3508.pdf
  * Shervashidze et al. [2009] 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 (2009). PMLR
  * Kriege et al. [2020] Kriege, N.M., Johansson, F.D., Morris, C.: A survey on graph kernels. Applied Network Science 5(1), 6 (2020) https://doi.org/10.1007/s41109-019-0195-3
  * Windels et al. [2022] Windels, S.F., Malod-Dognin, N., Pržulj, N.: Graphlet eigencentralities capture novel central roles of genes in pathways. PloS one 17(1), 0261676 (2022)
  * Aparício et al. [2019] Aparício, D., Ribeiro, P., Silva, F., Silva, J.: Finding dominant nodes using graphlets. In: COMPLEX NETWORKS, pp. 77–89 (2019). Springer
  * Klymko et al. [2014] Klymko, C., Gleich, D., Kolda, T.G.: Using triangles to improve community detection in directed networks. arXiv preprint arXiv:1404.5874 (2014)
  * Prat-Pérez et al. [2012] 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 . https://doi.org/10.1145/2396761.2398496
  * Friggeri et al. [2011] 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
  * Jabbour et al. [2018] 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
  * Chin et al. [2018] Chin, A.J., Gordon, G., MacPhee, K.J., Vincent, C.: Subtrees of graphs. Journal of Graph Theory 89(4), 413–438 (2018) https://doi.org/10.1002/jgt.22359 https://onlinelibrary.wiley.com/doi/pdf/10.1002/jgt.22359
  * Zhang et al. [2007] 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
  * Gaüzère et al. [2012] Gaüzère, B., Brun, L., Villemin, D.: Two new graphs kernels in chemoinformatics. Pattern Recognition Letters 33(15), 2038–2047 (2012) https://doi.org/10.1016/j.patrec.2012.03.020 . Graph-Based Representations in Pattern Recognition
  * Sun et al. [2022] Sun, D., Li, L., Liu, K., Wang, H., Yang, Y.: Enumeration of subtrees of planar two-tree networks. Applied Mathematics and Computation 434, 127404 (2022) https://doi.org/10.1016/j.amc.2022.127404
  * Wasa [2016] Wasa, K.: Enumeration of enumeration algorithms. CoRR abs/1605.05102 (2016) 1605.05102
  * Uno [2015] 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/%****␣main.bbl␣Line␣325␣****10.1007/978-3-319-21840-3_49 . https://doi.org/10.1007/978-3-319-21840-3_49
  * Niedermeier and Rossmanith [2000] Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parameter-tractable algorithms. Inf. Process. Lett. 73(3-4), 125–129 (2000)
  * Damaschke [2006] Damaschke, P.: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theoretical Computer Science 351(3), 337–350 (2006) https://doi.org/10.1016/j.tcs.2005.10.004 . Parameterized and Exact Computation
  * Wernicke [2005] 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)
  * Wernicke and Rasche [2006] 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 https://academic.oup.com/bioinformatics/article-pdf/22/9/1152/48840867/bioinformatics_22_9_1152.pdf
  * Pinar et al. [2017] 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/%****␣main.bbl␣Line␣400␣****10.1145/3038912.3052597 . https://doi.org/10.1145/3038912.3052597
  * Paredes and Ribeiro [2013] 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
  * Kashani et al. [2009] 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 Bioinformatics 10(1), 318 (2009) https://doi.org/10.1186/1471-2105-10-318
  * Melckenbeeck et al. [2017] 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 https://academic.oup.com/bioinformatics/article-pdf/34/8/1372/48915964/bioinformatics_34_8_1372.pdf
  * Ribeiro et al. [2021] 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) (2021) https://doi.org/10.1145/3433652
  * Ahmed et al. [2015] 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
  * Komusiewicz and Sommer [2020] Komusiewicz, C., Sommer, F.: Enumerating connected induced subgraphs: Improved delay and experimental comparison. Discrete Applied Mathematics (2020) https://doi.org/10.1016/j.dam.2020.04.036
  * Conte et al. [2023] 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)
  * Wang et al. [2024] Wang, S., Xiao, C., Casseau, E.: Algorithms with improved delay for enumerating connected induced subgraphs of a large cardinality. Information Processing Letters 183, 106425 (2024) https://doi.org/10.1016/j.ipl.2023.106425
  * Liu et al. [2021] Liu, X., Chen, Y.-Z.J., Lui, J.C., Avrachenkov, K.: Learning to count: A deep learning framework for graphlet count estimation. Network Science 9(S1), 23–60 (2021)
  * Read and Tarjan [1975] Read, R.C., Tarjan, R.E.: Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5(3), 237–252 (1975)
  * Birmelé et al. [2013] 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)
  * Tsukiyama et al. [1980] Tsukiyama, S., Shirakawa, I., Ozaki, H., Ariyoshi, H.: An algorithm to enumerate all cutsets of a graph in linear time per cutset. Journal of the ACM 27(4), 619–632 (1980)
  * Wasa and Uno [2018] 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)
  * Kurita et al. [2018] Kurita, K., Wasa, K., Uno, T., Arimura, H.: Efficient enumeration of induced matchings in a graph without cycles with length four. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences E101-A(9), 1383–1391 (2018)
  * Wasa and Uno [2018] 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)
  * Kurita et al. [2021] 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
  * Tarjan [1974] 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
  * Hopcroft and Tarjan [1973] 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
  * Conte et al. [2023] 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 . https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.21