Efficient Enumeration of Bipartite Subgraphs in
Graphs
Kunihiro Wasa1 and Takeaki Uno1

arXiv:1803.03839v1 [] 10 Mar 2018

National Institute of Informatics, Tokyo, Japan
{wasa, uno}@nii.ac.jp

Abstract. Subgraph enumeration problems ask to output all subgraphs
of an input graph that belongs to the specified graph class or satisfy the
given constraint. These problems have been widely studied in theoretical computer science. As far, many efficient enumeration algorithms for
the fundamental substructures such as spanning trees, cycles, and paths,
have been developed. This paper addresses the enumeration problem of
bipartite subgraphs. Even though bipartite graphs are quite fundamental and have numerous applications in both theory and application, its
enumeration algorithms have not been intensively studied, to the best of
our knowledge. We propose the first non-trivial algorithms for enumerating all bipartite subgraphs in a given graph. As the main results, we
develop two efficient algorithms: the one enumerates all bipartite induced
subgraphs of a graph with degeneracy k in O (k) time per solution. The
other enumerates all bipartite subgraphs in O (1) time per solution.
Keywords: Graph algorithms, subgraph enumeration, bipartite graphs,
constant delay, binary partition method, degeneracy

1

Introduction

A subgraph enumeration problem is, for given a graph G and a constraint R, to
output all subgraphs of G that satisfy R once for each and without duplication.
An example is to enumerate all the trees in the given graph, and all the subgraphs
whose minimum degree is at least k. The complexity and polynomiality of the
subgraph enumeration have been intensively studied in theoretical computer
science in the terms of both output size sensitivity and input size sensitivity.
Compared to optimization approach, enumeration has an advantage on exploring
and investigating all possibilities and all aspects of the data, thus is widely
studied in a practical point of view, e.g. Bioinformatics [1], machine learning [18],
and data mining [22,26]. We say that an enumeration algorithm is efficient if the
algorithm is output sensitive [11]. Especially, we say that A runs in polynomial
amortized time, if the total running time of an enumeration algorithm A is
O (N · poly(n)) time, where N is the number of solutions, n is the size of input,
and poly is a polynomial function. That is, A enumerates all solutions in poly(n)
time per solution. Such algorithms have been considered to be efficient, and
one of our research goals is to develop efficient enumeration algorithms. As far,

there have been studied enumeration algorithms for many fundamental graph
structures such as spanning trees [17,19], st-paths [7,17], cycles [2,8,17], maximal
cliques [3,6,15], minimal dominating sets [12], and so on. See the comprehensive
list in [23] of this area. Recently, Uno [21] developed a technique for a fine-grained
analysis of enumeration algorithms.
Bipartite graph is a well-known fundamental graph structure. A bipartite
graph is a graph containing no cycle of odd length, that is, whose vertex set
can be partitioned into two disjoint independent sets. Bipartite graphs widely
appears in real-world graphs such as itemset mining [22, 26], chemical information [13], Bioinformatics [27], and so on. Further, enumeration problems for
matchings [9, 10, 20] and bicqliue [4, 15] in bipartite graphs are well studied.
However, to the best of our knowledge, there has been proposed no non-trivial
enumeration algorithm for bipartite subgraphs.
In this paper, we propose efficient enumeration algorithms for bipartite induced subgraphs and bipartite subgraphs. For enumerating both substructures,
we employ a simple binary partition method, and develop a data structure for
efficiently updating the candidates that are called child generators. Intuitively
speaking, child generators are vertices or edges such that adding them to a current solution generates another solution. For bipartite induced subgraph, we look
at the degeneracy [14] of a graph. The degeneracy of a graph is the upper bound
of the minimum degree of any its subgraph, so the graph is sparse when the
degeneracy is small. It is a widely considered as a sparsity measure [3, 5, 24, 25].
There are several graph classes have constant degeneracies, e.g., forests, grid
graphs, planar graphs, bounded treewidth graphs, H-minor free graphs with
some fixed H, and so on [14]. In addition, Real-world graphs such as road networks, social networks, and internet networks are said to often have small degeneracies, or do so after removing a small part of vertices. Our algorithm utilizes
a good ordering on the vertices called a degeneracy ordering [16], that achieves
O (k) amortized time per solution, where k is the degeneracy of an input graph.
This implies that when we restrict the class of input graphs, such as planar
graphs, the algorithm runs in constant time per solution and is optimal in the
sense of time complexity. Next, for developing an algorithm for bipartite induced
subgraph, we show that we can avoid redundant edge additions and removal to
obtain a solution from another solution. As a main result, we give an optimal
enumeration algorithm, that is, the algorithm runs in constant time per solution.
These algorithms are quite simple, but by giving non trivial analysis, we show
the algorithms are efficient. These are the first non-trivial efficient enumeration
algorithms for bipartite subgraphs.

2

Preliminaries

Let G = (V, E) be an undirected graph with vertex set V = {1, . . . , n} and edge
set E = {(e1 , . . . , em } ⊆ V × V . An edge is denoted by e = (u, v). We say that
u and v are endpoints of e = (u, v), and u is adjacent to v if (u, v) ∈ E. When
the graph is undirected, (u, v) = (v, u). Two edges are said to be adjacent to

each other if a vertex is an end point of both edges. The set of neighbors of v is
the set of vertices that are adjacent to v and is denoted by N (v). For any vertex
subset S of V , E[S] = E ∩ (S × S), that is, E[S] is the set of edges whose both
endpoints are in S. For any edge subset F of E, V [F ] = {v ∈ V | ∃e ∈ F (v ∈ e)},
that is, V [F ] is the collection of endpoints of edges in F . The induced graph of
G by S is(S, E[S]) and is denoted by G[S]. G[F ] = (V [F ], F ) is a subgraph of
G by F . We denote by G \ S = G[V \ S]. Since G[S] (resp. G[F ]) is uniquely
determined by S (resp. F ), we identify S with G[S] (resp. F with G[F ]) if no
confusion arises.
We say that a sequence π = (v = w1 , . . . , w` = u) of vertices in V is a path of
G between v and u if for each i = 1, . . . , ` − 1, (wi , wi+1 ) ∈ E, and each vertex
in π appears exactly once. We denote by the length of a path the number of
edges in the path. π is a cycle if v = u and the length of π is at least three.
The distance dist (u, v) between u and v is the We say G is connected if there is
a path between any pair of vertices in G. G is bipartite if G has no cycle with
odd length. For a vertex subset S ⊆ V (resp. an edge subset F ⊆ E) such that
G[S] (resp. G[F ]) is bipartite, we say S (resp. F ) a bipartite vertex set (resp.
a bipartite edge set). For any bipartite vertex set S, if G[S] is connected, we
say S a connected bipartite vertex set. We also say a bipartite edge set F is a
connected bipartite edge set if G[F ] is connected. Let B V (G) and B E (G) be the
collection of connected bipartite vertex sets and connected bipartite edge sets,
respectively. We call B V (G) (resp. B E (G)) the solution space for Problem 1
(resp. for Problem 2). Since we only focus on connected ones, we simply call a
connected bipartite vertex (resp. edge) set a bipartite vertex (resp. edge) set.
In what follows, we assume that G is connected and simple. We now define the
enumeration problems of this paper as follows:
Problem 1 (Bipartite induced subgraph enumeration). For given a graph G, output all vertex sets in B V (G) without duplication.
Problem 2 (Bipartite subgraph enumeration). For given a graph G, output all
subgraphs in B E (G) without duplication.

3

Enumeration of Bipartite Induced Subgraphs

In this paper, we propose two enumeration algorithms for Problem 1 and Problem 2, and this section describes the algorithm for Problem 1. The pseudocode
of the algorithm is described in Algorithm 1. We employ binary partition method
for constructing the algorithms. The algorithm outputs the minimal solution to
be output, and partition the set of remaining solutions to be output into two
or more disjoint subsets. Then, the algorithm recursively solve the problems for
each subset, by generating recursive calls. We call this dividing step excluding
recursive calls (Line 11 in Algorithm 1) an iteration.
For any pair X and Y of iterations, X is the parent of Y if Y is called from
X and Y is a child of X if X is the parent of Y .

Algorithm 1: Enumeration algorithm based on binary method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Procedure Main(G = (V, E))
foreach v ∈ V do
Rec(G, {v} , N (v));
G ← G \ {v};
Subprocedure Rec(G, S, C (S, G))
output(S);
while C (S, G) 6= ∅ do
u ← the smallest child generator in C (S, G);
C (S, G) ← C (S, G) \ {u};
S 0 ← S ∪ {u};
Rec(G, S 0 , ComputeChildGen(C (S, G) , u, G));
G ← G \ {u};
Subprocedure ComputeChildGen(C (S, G) , u, G)
if u ∈ CL (S, G) then
C (S ∪ {u} , G) ← C (S, G) \ (CL (S, G) ∩ N (u));
else if u ∈ CR (S, G) then
C (S ∪ {u} , G) ← C (S, G) \ (CR (S, G) ∩ N (u));
C (S ∪ {u} , G) ← C (S ∪ {u} , G) ∪ Γ (S, u, G);
return C (S ∪ {v} , G);

Fig. 1. Example of the partitioning the solution space. Algorithm 1 recursively partitions the solution space BV (G, S) into smaller disjoint solution spaces, according to
C (S, G) = {u1 , . . . , u` }.

For any bipartite vertex set S, we say that S 0 is a child of S if there exists
a vertex u such that S 0 = S ∪ {u}. A vertex v ∈
/ S is a child generator of S
for G if S ∪ {v} is a bipartite vertex set in G. That is, the proposed algorithm
enumerates all bipartite vertex sets by recursively adding a child generator to
a current bipartite vertex set S. We denote by C (S, G) the set of child generators of S in G. Suppose that r be the smallest vertex in S. Let L (S) =
{u ∈ S | dist (u, r) mod 2 = 0} and R (S) = {u ∈ S | dist (u, r) mod 2 = 1}. For
any vertex v in G, any descendant iteration of Rec(G, {v} , N (v)) does not
output a bipartite vertex set including vertices less than v. Hence, no vertex
will never move to the other side in any descendant bipartite vertex set. Let
CL (S, G) = {u ∈ C (S, G) | u ∈ L (S ∪ {u})} and CR (S, G) = {u ∈ C (S, G) | u ∈ R (S ∪ {u})}.
Note that C (S, G) = CL (S, G) t CR (S, G),
 where A t B is the disjoint union
of A and B. We denote by B V (G, S) = S 0 ∈ B V (G) S ⊆ S 0 the collection
of bipartite vertex sets which include S. Note that B V (G) = B V (G, ∅). From

now on, we fix a graph G and a bipartite vertex set S of G. By the following
lemma, the algorithm divides B V (G, S) according to C (S, G) (Fig. 1). For an
edge u ∈ C (S, G), we define G(S, ≥ u) by G \ {v ∈ C (S, G) | v < u}.
Lemma 1. B V (G(S, ≥ u), S ∪ {u})∩B V (G(S, ≥ v), S ∪ {v}) = ∅ for any u 6= v
of C (S, G).
Proof. Without loss of generality, we can assume that u < v. Suppose that S 0 is
a bipartite vertex set in B V (G(S, ≥ u), S ∪ {u}) ∩ B V (G(S, ≥ v), S ∪ {v}). This
implies that S 0 includes both u and v. However, G(S, ≥ v) does not contain u.
Thus, S 0 ∈
/ B V (G(S, ≥ v), S ∪ {v}), and this contradicts the assumption. Hence,
the statement holds.
t
u
F
`
Lemma 2. B V (G, S) = {S} ∪ u∈C (S,G) B V (G(S, ≥ u), S ∪ {u}).
F`
Proof. If S 0 ∈ {S} ∪ u∈C (S,G) B V (G(S, ≥ u), S ∪ {u}), then S 0 is obviously
in B V (G, S). We assume that S 0 ∈ B V (G, S) and S 0 ) S. This implies that S 0
includes one of child generators in C (S, G). Let v be the smallest child generator
in C (S, G) such that v belongs to S 0 . Hence, S 0 ⊆ V (G(S, ≥ v)). Therefore,
S 0 ∈ B V (G(S, ≥ v), S) and the statement holds.
t
u
Next, we consider the correctness of ComputeChildGen. For brevity, we introduce some notations: Let u be a child generator in C (S, G). Γ (S, u, G) =
{w ∈ N (u) | w ∈
/ N [S]} is the set of vertices that are adjacent to only u in
S ∪{u}. Note that C (S, G)∩Γ (S, u, G) = ∅. ∆(S, G, u) = CL (S, G)∩N [u] if u ∈
CL (S, G); ∆(S, G, u) = CR (S, G)∩N [u] if u ∈ CR (S, G). Intuitively, Γ (S, u, G)
and ∆(S, G, u) are the set of vertices that are added to and removed from
C (S, G) to compute C (S ∪ {u} , G(G, ≥ u)), respectively. The following lemma
shows the sufficient and necessary conditions for computing C (S ∪ {u} , G(G, ≥ u)).
Lemma 3. C (S ∪ {u} , G(S, ≥ u)) = ((C (S, G) \ ∆(S, G, u)) t Γ (S, u, G))\{v ∈ C (S, G) | v < u} .
Proof. We let C∗ = ((C (S, G) \ ∆(S, G, u)) t Γ (S, u, G))\{v ∈ C (S, G) | v < u}.
Suppose that x ∈ C (S ∪ {u} , G(S, ≥ u)). Without loss of generality, we can assume that u ∈ CL (S, G). From the definition of G(S, ≥ u), x ∈
/ {v ∈ C (S, G) | v < u}.
If x ∈
/ N [S], then since x can be added to S ∪ {u}, x is adjacent to only
one vertex u in S ∪ {u}. Hence, x ∈ Γ (S, u, G). If x ∈ N [S], then since
x ∈ C (S ∪ {u} , G(S, ≥ u)), x ∈ C (S, G). Moreover, if x is in CL (S, G) ∩ N (u),
then S ∪ {u, x} has an odd cycle. Hence, the statement holds.
Suppose that x ∈ C∗ . Without loss of generality, we can assume that u ∈
CL (S, G). Since x ∈ C (S, G)tΓ (S, u, G), S 0 = S ∪{u, x} is connected. Suppose
that S 0 has an odd cycle Co . Since S ∪ {u} is bipartite, Co must contain x. This
implies that x has neighbors both in L (S 0 ) and R (S 0 ). If x ∈ Γ (S, u, G), then
x has exactly one neighbor in S 0 since u ∈ L (S ∪ {u}). Hence, x ∈ C (S, G).
This implies that either (I) N (x) ∩ (S ∪ {x}) ⊆ L (S) or (II) N (x) ∩ (S ∪ {x}) ⊆
R (S). If (I) holds, then x has neighbors only in L (S ∪ {u}) on S 0 since u ∈
CL (S, G) and x ∈ CR (S, G). If (II) holds, then then x has neighbors only in
R (S ∪ {u}) on S 0 since x ∈
/ N (u). Both cases contradict that x in Co . Hence,
x ∈ C (S ∪ {u} , G(S, ≥ u)) and the statement holds.
t
u

3

4

2
1

5
8

7

1

2

3

4

5

6

7

8

9

10

10

6

9

Fig. 2. An example of a degeneracy ordering of G. The degeneracy of G is two even
though there is a vertex with degree six. The right-hand side shows a degenerate
ordering of G. In the figure, if a vertex u is larger than a vertex v, then u is placed at
the right v. Each vertex has at most two larger neighbors.

From the above discussion, we can show the correctness of our algorithm.
Lemma 4. Algorithm 1 correctly enumerates all bipartite vertex sets in G.
Proof. From Line 7 to 12, the algorithm divides the solution space according to
C (S, G) as shown in Lemma 2. In addition, from Lemma 3, ComputeChildGen
correctly computes the sets of child generators of S 0 where S 0 is a child of S.
Hence, the statement holds.
t
u
3.1

Update of child generators

In this section, we consider the time complexity for the maintenance of the sets
of child generators. If we naı̈vely use Lemma 3 for ComputeChildGen, we can not
achieve O (k) amortized time per solution. To overcome this, we use a degeneracy
ordering on vertices. G is a k-degenerate graph [14] if for any induced graph S
of G, S has a vertex whose degree is at most k (Fig. 2). The degeneracy of
G is the smallest k such that G is k-degenerate. Every k-degenerate graph G
has a degeneracy ordering on V . The definition of a degeneracy ordering is that
for any vertex v in G, the number of neighbors of v that are larger than v is
at most k. By recursively removing a vertex with the minimum degree, we can
obtain this ordering in linear time [16]. Note that there are many degeneracy
orderings for a graph. In what follows, we pick one of degeneracy orderings of
G and then fix it as the vertex ordering of G. For any two vertices u, v in G, we
write u < v if u is smaller than v in the ordering. We can easily see that if u is
the smallest child generator, then u has at most k neighbors in G[C (S, G)] since
G[C (S, G)] is k-degenerate. Therefore, Lemma 3 implies that we can compute
the child generators of S ∪ {u} by removing at most k vertices and adding some
vertices that generate some grandchildren of S.
Next, we define the three types of neighbors of a vertex v in S, larger neighbors, visited smaller neighbors, and unvisited smaller neighbors: For any vertex
u ∈ N (v), (1) u is a larger neighbor of v if v < u, (2) u is a visited smaller
neighbor of v if u ∈ N [S] and u < v, and (3) u is an unvisited smaller neighbor otherwise (Fig. 3). Intuitively, u is a visited smaller neighbor if one of its
neighbor is already picked in some ancestor iteration of X which receives S. We

Fig. 3. Three types of neighbors of v. Here, VSN (v, S) = {u1 , u2 , u3 }, USN (v, S) =
{u4 , u5 }, and LN (v, S) = {u6 , . . . , u9 }. All of vertices in VSN (v, S) are adjacent to
some vertices in S. Thus, for any S ⊆ S 0 , if ui is in VSN (v, S), then ui is also in
VSN (v, S 0 ). In addition, Algorithm 1 also stores VSNC (v, S) and VSNC (v, S).

denote by LN (v, S), VSN (v, S), and USN (v, S) the sets of larger neighbors,
visited smaller neighbors, and unvisited smaller neighbors of v, respectively. In
addition, the algorithm divides VSN (v, S) into two disjoint parts VSNC (v, S)
and VSNC (v, S); VSNC (v, S) ⊆ C (S, G) and VSNC (v, S) ∩ C (S, G) = ∅. We
omit S if no confusion arises.
We now consider the data structure for the algorithm. For each vertex v, the
algorithm stores LN (v), VSNC (v), VSNC (v), and USN (v) in doubly linked
lists. C (S, G) is also stored in a doubly linked list and sorted by the degeneracy
ordering. The algorithm needs O (m) = O (kn) space for storing these data structures. The algorithm also records the modification when an iteration X calls a
child iteration Y . Let SX (resp. SY ) be bipartite vertex sets received by X (resp.
Y ). Note that for each neighbor w of a vertex v, if w moves from USN (v, SX )
to VSN (v, SY ), then w will never moves from the list in any descendant of Y .
Moreover, when w moves to VSN (v, SY ), w becomes a child generator of Y , and
thus, w ∈ VSNC (v, SY ). Initially, for all smaller neighbors of v is in USN (v, ∅).
In addition, v will be never added to the set in any descendant of S if v is not a
child generator of S. Hence, the algorithm totally needs O (m) space for storing
the modification history. When the algorithm backtracks to X from Y , the algorithm can completely restore the data structure in the same complexity as the
transition from X to Y . Now, we consider the time complexity for the transition
from X to Y . Suppose that when we remove a vertex v from C (S, G) or add v
to S, for each larger neighbor w of v, we give a flag which represents w is not
a child generator of the child of S. This can be done in O (k) time per vertex
because of the degeneracy. The next technical lemma shows the number of the
larger neighbors which are checked for updating the set of child generators.
Lemma 5. S has at most one larger neighbor of v for any vertex v in C (S, G).
Proof. Suppose that two or more neighbors of v are in S. Let x and y be two of
them such that y is added after x, and S 0 ⊆ S be an ancestor bipartite vertex set
/ S 0 . Without loss of generality,
of S for some graph G0 such that x ∈ S 0 and y ∈
we can assume that v and y are child generators of S 0 . We can also assume that

v is added after y. Then, from Lemma 3, When y is added to S 0 , v is not in
G(G0 , ≥ y) since v < y. This contradicts, and thus, the statement holds.
t
u
Lemma 6. Let u and v be two vertices in C (S, G) such that u < v and @w ∈
C (S, G) (u < w < v). C (S ∪ {v} , G(S, ≥ v)) can be computed from C (S ∪ {u} , G(S, ≥ u))
in O (k |C (S ∪ {u} , G(S, ≥ u))| + k |C (S ∪ {v} , G(S, ≥ v))|) time.
Proof. From Lemma 3, only the neighbors of v or u may be added to or removed
from C (S ∪ {u} , G(S, ≥ u)) to obtain C (S ∪ {v} , G(S, ≥ v)). Let w be a vertex
in LN (v). We consider the following cases: (L.1) w ∈ C (S ∪ {u} , G(S, ≥ u)) ∩
C (S ∪ {v} , G(S, ≥ v)) or w ∈
/ C (S ∪ {u} , G(S, ≥ u)) ∪ C (S ∪ {v} , G(S, ≥ v)).
In this case, there is nothing to do. (L.2) w ∈ C (S ∪ {u} , G(S, ≥ u))\C (S ∪ {v} , G(S, ≥ v)).
For each larger neighbor x of w, we need to move w from VSNC (x, S ∪ {u})
to VSNC (x, S ∪ {v}). The number such x is at most k |C (S ∪ {u} , G(S, ≥ u))|.
(L.3) w ∈ C (S ∪ {v} , G(S, ≥ v))\C (S ∪ {u} , G(S, ≥ u)). For each larger neighbor x of w, we need to move w from VSNC (x, S ∪ {u}) to VSNC (x, S ∪ {v}).
The number of such x is at most k |C (S ∪ {v} , G(S, ≥ v))|. Note that for each
vertex, at most one larger its neighbor is in S from Lemma 5. Thus, the above
three conditions can be checked in constant time for each w by checking whether
or not w is in the same partition as v. Therefore, the larger part can be done in
O (k + k |C (S ∪ {u} , G(S, ≥ u))| + k |C (S ∪ {v} , G(S, ≥ v))|) time.
Next, let w be a vertex in VSNC (v, S). From Lemma 3, such w does not
belongs to C (S ∪ {v} , G(S, ≥ v)). Moreover, since u and v are consecutive on
C (S, G), such w is also not in C (S ∪ {u} , G(S, ≥ u)). Thus, this case can be
done in constant time by skipping such vertices. For each vertex w in VSNC (v, S),
w can not be added to both S ∪ {u} and S ∪ {v}. Hence, we skip them. In addition, we need to remove v from G(S, ≥ u). This takes O (k) time since we only
need to update larger neighbors of v. The same procedure needs for updating
the neighbors of u. Hence, the statement holds.
t
u
Roughly speaking, by ignoring neighbors of u or v such that they can not
be added to both S ∪ {u} and S ∪ {v}, we can compute C (S ∪ {v} , G(S, ≥ v))
from C (S ∪ {u} , G(S, ≥ u)), efficiently. In addition, other neighbors have corresponding bipartite vertex sets with size |S| + 2, that is, grandchildren of S. This
implies that we can amortize the cost for these neighbors as follows.
Lemma 7. Let u be a vertex in C (S, G) and T (S, u) be the computation time for
C (S ∪ {u} , G(S, ≥ u)). The total computation time for all theP
sets of child generators of S’s children and recording the modification history is u∈C (S,G) T (S, u) =


P
O k |C (S, G)| + u∈C (S,G) k |C (S ∪ {u} , G(S, ≥ u))| time.
Proof. From Lemma 3, we need O (k |C (S, G)| + k |C (S ∪ {u∗ } , G(S, ≥ u∗ ))|)
time for computing C (S ∪ {u∗ } , G(S, ≥ u∗ )), where u∗ is the smallest child generator in C (S, G). From Lemma 6, we can
compute all the sets of child generators
P

for children of S except for S∪{u∗ } in O
k
|C
(S
∪
{u}
,
G(S,
≥
u))|
u∈C (S,G)
time in total. Moreover, recording the modification history can be done in the
same time complexity in above. Hence, the statement holds.
t
u

Theorem 1. Given a graph
 G with degeneracy k, Algorithm 1 enumerates all
solutions in O k B V (G) total time, that is, O (k) time per solution with
O (m) = O (kn) space and preprocessing time.
Proof. From Lemma 7, we can see the larger neighbors of u are always checked.
Thus, Line 12 can be done in O (k) time since the algorithm does not need to remove edges whose endpoints are u and a smaller neighbor of u. Moreover, Line 9
can be done in O (1) time. In addition, in the preprocessing, we need to initialize
the data structure and compute the degeneracy ordering. The both need O (kn)
time and space since the number of edges is at most
Lemma 7 and the
P kn. From

P
above this discussion, the algorithm runs in O
S∈BV (G)
u∈C (S,G) T (S, u)
P


P
time. Now, O
|C
(S,
G)|
+
|C
(S
∪
{u}
,
G(S,
≥
u))|
=
V
S∈B (G)
u∈C (S,G)

V
O B (G) . Hence, the statement holds.
t
u
Corollary 1. All bipartite induced subgraphs in graphs with constant degeneracy, such as planar graphs, can be listed in O (1) time per solution with O (n)
space and preprocessing time.

4

Enumeration of Bipartite Subgraphs

In this section, we describe our algorithm for Problem 2. For a graph G and
a bipartite edge set F of G, let B(G, F ) be the set of edges e of G such
that F ∪ {e} is not
 bipartite, i.e., F ∪ {e} has an odd cycle that includes e.
Let B E (G, F ) = F 0 ∈ B E (G) F ⊆ F 0 . We can see that B E (G(F ), F ) =
0
B E (G(F ) \ B(G,
S F ),0 F ). For an edge e of G, we define N (G, e) = {f ∈ 0E \ {e} | f is adjacent to e},
0
N (G, F ) = e∈F N (e)\F , and we also define G(F, ≥ e) by G\{f ∈ N (G, F ) | f < e}.
The framework of the algorithm is the same as the algorithm for Problem 1.
The algorithm starts from the empty edge set, and add edges recursively so that
the edge sets generated are always connected and bipartite, and no duplication
occurs. For given a graph G and a bipartite edge set F of G, the algorithm
first removes edges of B(G, F ) from G, and outputs F as a solution. Then for
each e ∈ N 0 (G, F ), the algorithm generates the problems of enumerating all
bipartite subgraphs that include F ∪ {e} but no edge f < e, f ∈ N 0 (G, F ), that
is, bipartite subgraphs in G(F, ≥ e) that includes F ∪ {e}. Before generating the
recursive call, the algorithm computes the edges of B(G(F, ≥ e), F ∪ {e}) and
removes them from G(F, ≥ e) so that the computation of the iteration will be
accelerated. The correctness of our strategy for the enumeration is as follows.
Lemma 8. B E (G(F, ≥ e), F ∪ {e}) ∩ B E (G(F, ≥ f ), F ∪ {f }) = ∅ for any e 6=
f of N 0 (G, F ).
Proof. Suppose that F 0 is a bipartite edge set in B E (G(F, ≥ e), F ∪ {e}) ∩
B E (G(F, ≥ f ), F ∪ {f }). This implies F 0 includes ei and ej . However, Gj does
not include ei , and thus this contradicts the assumption. Note that the addition
of an edge of N 0 (G, F ) never results non-bipartite since we removed all edges of
B(G, F ) from G.
t
u

Algorithm 2: Enumeration algorithm for bipartite edges sets
1
2
3
4
5
6
7
8
9
10
11
12
13

Procedure Main(G = (V, E))
foreach e ∈ E do // Pick the smallest edge in E.
Rec(G, {e} , N (e));
G ← G \ {e};
Subprocedure Rec(G, F, N 0 (F, G))
output(F );
while N 0 (F, G) 6= ∅ do
e ← the smallest child generator in N 0 (F ) G;
F 0 ← F ∪ {e};
G0 ← G(F, ≥ e) \ E(B(G(F, ≥ e), F 0 ));
N 0 (G0 , F 0 ) ←
(N 0 (G, F ) ∪ N+ (G, F, e)) \ (N− (G, F, e) ∪ {f ∈ E | f ≤ e});
Rec(G0 , F 0 , N 0 (G0 , F 0 ));
N 0 (F, G) ← N 0 (F, G) \ {e};

Lemma 9. B E (G, F ) = {F } ∪

F

e∈N 0 (G,F )

B E (G(F, ≥ e), F ∪ {e}),

Proof. Let F 0 , F ⊂ F 0 be a bipartite edge set in B E (G, F ), and e be the smallest
edge among F 0 ∩ N 0 (G, F ). e always exists since F 0 is connected. We can see
that F 0 ∈ B E (G(F, ≥ e), F ∪ {e}), thus the statement holds.
t
u
For the efficient computation, our algorithm always keep N 0 (G, F ) in the
memory and update and pass it to the recursive calls. For the efficient update
of N 0 (G, F ), we keep the graph G \ F in the memory since edges of F never
be added to N 0 (G, F ), until the completion of the iteration. We also put a
label of “1” or “2” to each vertex in V (F ) and update so that each edge of F
connects vertices of different labels, that is always possible since F is bipartite.
For a vertex v of G that is not in V (F ), let N1 (G, F, v) (resp., N2 (G, F, v)) be
the set of edges f of N (v) \ F such that the endpoint of f other than v has
label “1” (resp., “2”). We also keep and update N1 (G, F, v) and N2 (G, F, v).
For an edge (u, v) ∈ N 0 (G, F ) such that u ∈
/ V (F ), we define N+ (G, F, (u, v))
by N1 (G, F, v) and N− (G, F, (u, v)) by N2 (G, F, v) if the label of v is “1”, and
N+ (G, F, (u, v)) by N2 (G, F, v) and N− (G, F, (u, v)) by N1 (G, F, v) otherwise.
We define N1 (G, F, (u, v)) and N2 (G, F, (u, v)) by the empty set if both u and v
are in V (F )
For an edge e ∈ N 0 (G, F ), let F 0 = F ∪ {e} and G0 be the graph obtained
from G(F, ≥ e) by removing edges of B(G(F, ≥ e), F 0 ).
Lemma 10. Suppose that B(G, F ) = ∅ and e = (u, v). Then, B(G0 , F 0 ) =
N− (G, F, v).
Proof. Since B(G, F ) = ∅, any edge f in B(G0 , F 0 ) must share one of its endpoint
with e, and the endpoint is adjacent to no edge of F . Further, the edge is not
included in F . The addition of f to F generates an odd cycles if and only if the
label of both endpoints of f are the same. Therefore the statement holds.
t
u

The following lemma shows that the computation of N 0 (G0 , F 0 ) from N 0 (G, F )
can be also done in O (|N+ (G, F, e)| + 1) time.
Lemma 11. N 0 (G0 , F 0 ) = (N 0 (G, F ) ∪ N+ (G, F, e))\(N− (G, F, e) ∪ {f ∈ E | f ≤ e}) .
Proof. We first prove N 0 (G0 , F 0 ) ⊆ (N 0 (G, F ) ∪ N+ (G, F, e))\(N− (G, F, e) ∪ {f ∈ E | f ≤ e}).
Let f be an edge in N 0 (G0 , F 0 ). Then, f is in either N 0 (G, F ) or N+ (G, F, e).
From the definition of G(F, ≥ e) and B(G0 , F 0 ), f is not in B(G0 , F 0 ). Further, f > e from f ∈ G0 . This implies that f ∈ (N 0 (G, F ) ∪ N+ (G, F, e)) \
(N− (G, F, e) ∪ {f ∈ E | f ≤ e}).
We next prove (N 0 (G, F ) ∪ N+ (G, F, e)) \ (N− (G, F, e) ∪ {f ∈ E | f ≤ e}) ⊇
0
N (G0 , F 0 ) . Suppose that f ∈ (N 0 (G, F ) ∪ N+ (G, F, e))\(N− (G, F, e) ∪ {f ∈ E | f ≤ e}).
Then, f is not in F 0 , and adjacent to an edge of F 0 . Further, f > e and the addition of f to F 0 generates no odd cycle. Thus, f ∈ N 0 (G0 , F 0 ).
t
u
When we generate G(F, ≥ e) for each e ∈ N 0 (G, F ) one by one in increasing
order, the total computation time is O (|N 0 (G, F )|). Computation of G0 \F 0 is at
most the time to compute G0 . From this together
with these lemmas, we can see 

P
0
that an iteration of the algorithm spends O |N (G, F )| + e∈N 0 (G,F ) |N+ (G, F, e)|
time. The following lemma bound this complexity in another way. Let Ge is the
graph obtained from G(F ∪ {e} , ≥ e) by removing edges of B(G(F ∪ {e} , ≥
e), F ∪ {e}).
Lemma 12. Suppose that e0 is next to e in the edge ordering in N 0 (G, F ).
The computation of N 0 (Ge0 , F ∪ {e0 }) from N 0 (Ge , F ∪ {e}) can be done in
O (|N 0 (Ge0 , F ∪ {e0 })| + |N 0 (Ge , F ∪ {e})|) time.
Proof. The computation is to recover N 0 (G, F )\{f ∈ E | f ≤ e} from N 0 (Ge , F ∪ {e})
and construct N 0 (Ge0 , F ∪ {e0 }) from it. From Lemma 11, its time is linear in
|N+ (G, F, e) \ {f ∈ E | f ≤ e}|+|N− (G, F, e) \ {f ∈ E | f ≤ e}|+|N+ (G, F, e0 ) \ {f ∈ E | f ≤ e}|+
|N− (G, F, e0 ) \ {f ∈ E | f ≤ e}|. We see that N+ (G, F, e) \ {f ∈ E | f ≤ e} ⊆
N 0 (Ge , F ∪ {e}), and N+ (G, F, e0 )\{f ∈ E | f ≤ e0 } ⊆ N 0 (Ge0 , F ∪ {e0 }). When
N− (G, F, e) 6= N− (G, F, e0 ), we have N− (G, F, e)∩N− (G, F, e0 ) = ∅, thus N− (G, F, e)\
{f ∈ E | f ≤ e} ⊆ N 0 (Ge0 , F ∪ {e0 }), and N− (G, F, e0 )\{f ∈ E | f ≤ e0 } ⊆ N 0 (Ge , F ∪ {e})
thus the statement holds. When N− (G, F, e) = N− (G, F, e0 ), they are canceled
out and no need of taking care in the computation, thus the statement also holds.
t
u
Lemma 13. For any iteration inputting G and F such that B(G, F ) = ∅, its
computation time is at most proportional to one plus the number of its children
and the grandchildren.
Proof. For the first recursive call with respect to an edge e, we pay computation
time of O (|N 0 (G, F )| + |N 0 (Ge , F ∪ {e})|). For the remaining recursive calls, as
we see in Lemma 12, the computation time is linear in the number of grandchildren generated in the recursive call, and that generated just before. Thus, the
statement holds.
t
u

Sine any iteration requires at most O (|V | + |E|) space. When the iteration
generates a recursive call, the graphs and variants that the iteration is using has
to be recovered, just after the termination of the recursive call. This can be done
just keeping the vertices and edges that are removed to make the input graph of
the recursive call. Thus, the total accumulated space spent by all its ancestors
is at most O (|V | + |E|). Therefore, we obtain the following theorem.
Theorem 2.
 All bipartite subgraphs in a graph G = (V, E) can be listed in
O B E (G) total time, that is, O (1) time per solution with O (|V | + |E|) space.

References
1. N. K. Ahmed, J. Neville, R. A. Rossi, and N. Duffield. Efficient graphlet counting
for large networks. In ICDM 2015, pages 1–10, 2015.
2. E. Birmelé, R. Ferreira, R. Grossi, A. Marino, N. Pisanti, R. Rizzi, and G. Sacomoto. Optimal Listing of Cycles and st-Paths in Undirected Graphs. In SODA
2012, pages 1884–1896, 2012.
3. A. Conte, R. Grossi, A. Marino, and L. Versari. Sublinear-Space Bounded-Delay
Enumeration for Massive Network Analytics: Maximal Cliques. In ICALP 2016,
volume 55 of LIPIcs, pages 148:1–148:15, 2016.
4. V. M. Dias, C. M. de Figueiredo, and J. L. Szwarcfiter. Generating bicliques of a
graph in lexicographic order. Theor. Comput. Sci., 337(1-3):240–248, 2005.
5. D. Eppstein, M. Löffler, and D. Strash. Listing all maximal cliques in sparse graphs
in near-optimal time. In ISAAC 2010, volume 6506 of LNCS, pages 403–414, 2010.
6. D. Eppstein and D. Strash. Listing All Maximal Cliques in Large Sparse Real-world
Graphs. In SEA 2011, LNCS 6630, pages 364–375, 2011.
7. R. Ferreira, R. Grossi, and R. Rizzi. Output-sensitive listing of bounded-size trees
in undirected graphs. In ESA 2011, volume 6942 of LNCS, pages 275–286, 2011.
8. R. Ferreira, R. Grossi, R. Rizzi, G. Sacomoto, and S. Marie-France. Amortized
Õ(|v|)-delay algorithm for listing chordless cycles in undirected graphs. In ESA
2014, volume 8737 of LNCS, pages 418–429, 2014.
9. K. Fukuda and T. Matsui. Finding all the perfect matchings in bipartite graphs.
Appl. Math. Lett., 7(1):15–18, jan 1994.
10. A. Gély, L. Nourine, and B. Sadi. Enumeration aspects of maximal cliques and
bicliques. Discrete Appl. Math., 157(7):1447–1459, apr 2009.
11. D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou. On generating all maximal independent sets. Inform. Process. Lett., 27(3):119–123, 1988.
12. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. Enumeration of Minimal Dominating Sets and Variants. In FCT 2011, LNCS 6914, pages 298–309, 2011.
13. S. Koichi, M. Arisaka, H. Koshino, A. Aoki, S. Iwata, T. Uno, and H. Satoh. Chemical structure elucidation from 13c nmr chemical shifts: Efficient data processing
using bipartite matching and maximal clique algorithms. J. Chem. Inf. Model.,
54(4):1027–1035, 2014.
14. D. R. Lick and A. T. White. k-degenerate graphs. Canadian J. Math., 22(5):1082–
1096, 1970.
15. K. Makino and T. Uno. New algorithms for enumerating all maximal cliques. In
SWAT 2004, volume 3111 of LNCS, pages 260–272, 2004.
16. D. W. Matula and L. L. Beck. Smallest-last ordering and clustering and graph
coloring algorithms. J. ACM, 30(3):417–427, 1983.

17. R. C. Read and R. E. Tarjan. Bounds on backtrack algorithms for listing cycles,
paths, and spanning trees. Networks, 5(3):237–252, 1975.
18. S. Ruggieri. Enumerating distinct decision trees. In ICML 2017, volume 70 of
Proceedings of Machine Learning Research, pages 2960–2968, 2017.
19. A. Shioura, A. Tamura, and T. Uno. An Optimal Algorithm for Scanning All
Spanning Trees of Undirected Graphs. SIAM J. Comput., 26(3):678–692, 1997.
20. T. Uno. Algorithms for enumerating all perfect, maximum and maximal matchings
in bipartite graphs. In ISAAC 1997, volume 1350 of LNCS, pages 92–101, 1997.
21. T. Uno. Constant time enumeration by amortization. In WADS 2015, volume 9214
of LNCS, pages 593–605, 2015.
22. T. Uno, M. Kiyomi, and H. Arimura. LCM ver. 2: Efficient mining algorithms for
frequent/closed/maximal itemsets. In FIMI ’04, 2004.
23. K. Wasa. Enumeration of enumeration algorithms. CoRR, abs/1605.05102, 2016.
24. K. Wasa, H. Arimura, and T. Uno. Efficient Enumeration of Induced Subtrees in a
K-Degenerate Graph. In ISAAC 2014, volume 6506 of LNCS, pages 94–102, 2014.
25. Y. Xu, J. Cheng, and A. W.-C. Fu. Distributed Maximal Clique Computation and
Management. IEEE T. Serv. Comput., 9(1):1–1, 2015.
26. M. J. Zaki. Scalable algorithms for association mining. IEEE T. Knowl. Data.
En., 12(3):372–390, 2000.
27. Y. Zhang, C. A. Phillips, G. L. Rogers, E. J. Baker, E. J. Chesler, and M. A.
Langston. On finding bicliques in bipartite graphs: a novel algorithm and its
application to the integration of diverse biological data types. BMC Bioinformatics,
15(1):110, 2014.

