TCS -TR-A-14-76

TCS Technical Report

Frontier-based Search for Enumerating All
Constrained Subgraphs with Compressed
Representation
byJun Kawahara, Takeru Inoue, Hiroaki Iwashita andShin-ichi Minato
Division of Computer Science
Report Series A
September 30, 2014

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Frontier-based Search for Enumerating All Constrained
Subgraphs with Compressed Representation
Jun Kawahara1

Takeru Inoue2
Shin-ichi Minato4,5

Hiroaki Iwashita3

1

Graduate School of Information Science, Nara Institute of Science and Technology
jkawahara@is.naist.jp
2
NTT Network Innovation Laboratories, NTT Corporation
inoue.takeru@lab.ntt.co.jp
3
Knowledge Platforms Laboratory, Fujitsu Laboratories Limited
iwashita.hiroak@jp.fujitsu.com
4
Graduate School of Information Science and Technology, Hokkaido University, Japan
minato@ist.hokudai.ac.jp
5
ERATO MINATO Project, Japan Science and Technology Agency, Japan

Abstract
For the subgraph enumeration problem, there have been proposed very
eﬃcient algorithms whose time complexities are far less than the number ofsubgraphs. Although the number of subgraphs can increase exponentially withthe graph size, they exploit compressed representations to maintain enumerated subgraphs compactly so as to reduce the time complexity. However, they
are designed for enumerating a specific type of subgraphs only, e.g., paths ortrees. In this paper, we propose a novel algorithm framework, called frontierbased search, which generalizes these specific algorithms without losing theireﬃciency. We believe that our frontier-based search will be used to resolve
various practical problems that include complicated subgraph enumeration.

1

Introduction

Enumerating all the subgraphs of a graph (or, more generally, object) satisfying
given conditions is one of the most fundamental problems in combinatorics andgraph theory. A few decades ago, several well-known algorithms were proposed for
subgraph enumeration problems [16, 19, 1]. Since these traditional enumeration
algorithms output subgraphs one by one, their time complexities are proportional
to the output size. The output size, however, can increase exponentially with thegraph size. Recently, several algorithms whose time complexities are significantly
smaller than the output size have been proposed [18, 12, 9]; these algorithms exploit
compressed representations such as binary decision diagrams (BDDs) [3] in orderto output the subgraphs in a compressed manner.
12

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato

Figure 1 is an example of s-t path enumeration that shows the key idea on theuse of compressed representation. Since traditional naı̈ve algorithms output s-tpaths one by one (Figure 1 (b)), the time complexity of the algorithms depends
on the number of s-t paths, which exponentially increases as the size of the graphgrows. Regarding a path as a set of edges constituting the path, we find some paths
share a common subset of edges; e.g., the first and second paths share edges 12, 23,
36, 56, and 89 in Figure 1 (b). We merge such common edges if possible, as shown in
Figure 1 (c); in this compressed diagram, each path can be retrieved walking fromthe left to the right. As shown in the figure, compressed representation requires
only 30 edges to represent all the paths (Figure 1 (c)), while naı̈ve enumeration
includes 64 edges with many duplications (Figure 1 (b)). Recent enumeration
algorithms directly construct the compressed representation from the left to theright, without detouring the naı̈ve representation. If the compressed representation
is much smaller than the naı̈ve representation, the time complexity can be reduced
a lot.
Subgraph enumeration algorithms can play a key role in practical problems including logic puzzles [21], reliability evaluation [4], and network optimization [7].
Unfortunately, subgraph enumeration algorithms used in these problems are dedicated for their own problems, and so we have to develop yet another graph enumeration algorithm to deal with every new problem. In order to resolve several
practical problems, enumeration algorithms must be so flexible to search for varietyof complicated subgraphs, such as “forests such that each tree contains exactly oneof the specified vertices and the number of its edges is in the specified range.” Our
key contribution is generalization of algorithms that find common parts between
subgraphs so as to construct the compressed representation for various types of
constrained subgraphs, like Figure 1 (c).
In this paper, we propose a subgraph enumeration algorithm, called frontierbased search, which enables us to enumerate various types of constrained subgraphs.
Frontier-based search supports several primitive constraints including a set of connected vertices, degree of each vertex, acyclic or not, and the number of edges
used. Combinations of these primitive constraints allow us to specify various typesof complicated subgraphs. To recap, the frontier-based search has the following
features:
1. Unlike recent specific enumeration algorithms, frontier-based search supports
several primitive constraints, and allows us to specify various types of subgraphs by their combinations.
2. Unlike traditional naı̈ve enumeration algorithms, frontier-based search inherits the excellent properties of recent subgraph enumeration algorithms, suchas great compression ability and eﬃcient search strategy without backtracks(the worst case complexity is not excellent theoretically, but frontier-based
search performs well practically if subgraphs have some structure).

Frontier-based Search for Enumerating All Constrained Subgraphs

3(a) 3x3 grid graph!
v1!

v2!

v3!

v4!

v5!

v6!

v7!

v8!

v9!

(b) Enumerating all paths naively!
!"#!"$!!!!$%!!!!&'!&(!%)!')!!!!(*!!!!*+!
!$#!"$!!!!$%!!!!!!!!!!%)!')!'*!!!!!!!*+!
!%#!"$!!!!$%!!!!!!!!!!%)!!!!!!!!!!)+!
!&#!"$!!!!!!!$'!&'!&(!!!!!!!!!!(*!!!!*+!
!'#!"$!!!!!!!$'!!!!!!!!!!')!!!!!!!)+!
!)#!"$!!!!!!!$'!!!!!!!!!!!!!'*!!!!!!!*+!
!(#!!!!"&!$%!$'!&'!!!!%)!!!!!!!!!!)+!
!*#!!!!"&!$%!$'!!!!&(!%)!!!!'*!(*!)+!
!+#!!!!"&!!!!!!!&'!!!!!!!')!!!!!!!)+!
",#!!!!"&!!!!!!!&'!!!!!!!!!!'*!!!!!!!*+!
""#!!!!"&!!!!!!!!!!&(!!!!')!'*!(*!)+!
"$#!!!!"&!!!!!!!!!!&(!!!!!!!!!!(*!!!!*+!
(c) Enumeration with compressed representation!
!"!

#%! #&!$'! %'!
&(!
$'!%'! %(!

"$!

()!

"%!#%!#&!
%(!
%'!
')!
!#!"$!"%!#%!
$'!
#&!$'! %(!&(!
%'!
#%!
#&!

%'!

Figure 1: Enumerating all twelve v1 -v9 paths on 3×3 grid graph naı̈vely and using
compressed representation. A path is represented by a set of edges; e.g., the first path “12,23, 45, 47, 36, 56, 78, and 89” means path of {{v1 , v2 }, {v2 , v3 }, {v4 , v5 }, {v4 , v7 }, {v3 , v6 },{v5 , v6 }, {v7 , v8 }, and {v8 , v9 }}.

The organization of the paper is as follows. In Section 2, we analyze the Simpath enumeration algorithm [9, exercise 225 in Section 7.1.4], in order to clarify
requirements to frontier-based search. In Section 3, we propose the frontier-based
search that enumerates various subgraphs, and also present some examples of subgraphs which can be treated. Section 4 shows several experimental results. Related
work is shown in Section 5.

2

Analyzing Simpath

Simpath is an enumeration algorithm designed for all the s-t paths on a given
graph. It is proposed by Knuth, and the implementation is highly-optimized.
This section unravels the secret of eﬃciency, and summarizes requirements to ourfrontier-based search.

4

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato

2.1

OutlineSimpath enumerates all the s-t paths on a given undirected graph; this graph iscalled the universe and is denoted by Guni = (Vuni , Euni ), where Vuni is a set of vertices and Euni is a set of edges. Let n = |Vuni |, m = |Euni |, Vuni = {v1 , . . . , vn }, and′ }, {e′ , e′ , . . . , e′ })Euni = {e1 , . . . , em }. An s-t path is a subgraph ({v1′ , v2′ , . . . , vl+1
1 2
l
′
′
′
′
′
′ } ∈ Eof Guni such that v1 = s, vl+1 = t, vi ∈ Vuni for all i, ei = {vi , vi+1
uni for alli, and vi ̸= vj for all i and j with i ̸= j.
Simpath constructs the directed acyclic graph which is the compressed representation to compactly represent all the s-t paths on Guni (see Figure 2). We call it
the decision diagram (DD) 1 and denote by D = (N, A). We describe the property
which D has to possess, and then we outline the construction process of D. To
avoid confusing Guni with D, we address elements in Vuni and Euni as a vertex andan edge, respectively, whereas ones in N and A as a node and an arc, respectively.
Also, we call a path on D a route.
D has a root node, denoted by nroot , which is labeled e1 and which has just two
arcs, called a 0-arc and a 1-arc (this property is diﬀerent with Figure 1 (c), which
has only a single type of arcs). The 0-arc and the 1-arc mean not selecting andselecting e1 , respectively. Each arc points at a node labeled e2 , or a special node,called a terminal node, which is labeled 0 or 1. Similarly, for each i = 1, . . . , m − 1,a node labeled ei has a 0-arc and a 1-arc, each of which points at a node labeled
ei+1 or a terminal node. Both arcs of any node labeled em have to point at 0 or
1. For each route from nroot to 1 in D, labels of nodes whose 1-arc is included in
the route have to constitute an s-t path on Guni .
Although arbitrary binary tree with appropriate terminals satisfies the requirements of the DD described above (e.g., Figure 2 (b)), the number of nodes of thebinary tree for a graph with m edges can increase exponentially as m grows. If
there exist two nodes labeled ei whose subtrees are identical, we need not to maintain both of them. More precisely, for nodes n1 and n2 in a DD, n1 and n2 are
identical if R(n1 ) = R(n2 ) holds, where R(n̂) is the set of edge sets corresponding
to all the route from n̂ to 1. In this case, the operation of keeping n1 , discarding
n2 and modifying the destination of each arc which points at n2 into n1 does notchange the set of s-t paths which the DD represents. We call this operation node
sharing. The DD in Figure 2 (c) is obtained by repeatedly applying node sharing
to the binary tree in Figure 2 (b) as far as possible. Observe that it satisfies therequirements of the DD.
We directly construct the DD such as Figure 2 (c) in a top-down and breadthfirst manner without making the broad binary tree such as Figure 2 (b). We firstcreate nroot , a 0-arc and a node labeled e2 , and connect nroot with the node using
the 0-arc. We also create a 1-arc and a node labeled e2 , and connect nroot with thenode using the 1-arc. Similarly, for i = 1, . . . , m − 1, we create nodes labeled ei+1
1
The DD which we will construct is known as a zero-suppressed ordered binary decision diagram(ZDD) [11]. Note that it may not be reduced.

5

Frontier-based Search for Enumerating All Constrained Subgraphsn
e1 rootsn
e1 root

e2
e2

e1
e3
e4
t
(a)

e3

e2
e3

e3

e2
e3

e3

e2
e3

e3

e4 e4 e4 e4 e4 e4 e4 e4e4

e4

0000000101000000
(b)

0

1
(c)

Figure 2: Example of the DDs representing all the s-t paths on a graph. (a) An example
of an universe. There are two s-t paths, {e1 , e4 } and {e2 , e3 , e4 } on the graph. (b) The
broad binary tree representing the set of the paths. 0-arcs and 1-arcs are depicted as dottedand solid lines, respectively. (c) The DD obtained from (b) by repeating node sharing.
Observe that by selecting either 1-arc, 0-arc, 0-arc and 1-arc, or 0-arc, 1-arc, 1-arc and1-arc in this order, we reach 1 from nroot .

after creating all the nodes labeled ei . When making a node labeled ei+1 , we check
whether there is an existing node which is identical with the node or not, and we
perform node sharing if found. Note that deciding whether nodes n1 and n2 are
identical has to be carried out without constructing children of n1 and n2 , which
will be discussed in Section 2.2. This is the key technique that makes Simpath
very eﬃcient.
The pseudocode of Simpath can be written as shown in Algorithm 1. In Line 513, for x = 0, 1, the x-arc of n̂ is made to point at a new node, an existing node or aterminal, as follows. In Line 5, CheckTerminal(n̂, i, x) decides whether the destination of the x-arc of n̂ is a terminal (0, 1) or not. In Line 8, UpdateInfo(n′ , i, x)
updates the information of n′ , as will be described later. Line 9 searches an existing node n′′ which is identical to n′ . If it is found, n′ is discarded and let the x-arc
of n̂ point at n′′ . In Line 12, the new node n′ is added to Ni+1 , where Nj denotes
the set of nodes labeled with ej . In Algorithm 1, we put processes depending on
s-t paths into UpdateInfo and CheckTerminal functions. By rearranging Simpath in this way, we find that other enumeration algorithms designed for diﬀerent
graph types also can be written in the same manner with diﬀerent specificationsof UpdateInfo and CheckTerminal.

2.2

Finding Child Nodes

In this subsection, we analyze the two functions, UpdateInfo and CheckTerminal,
which are specialized to handle s-t paths. In order to find child nodes without constructing the subtree, each node maintains some values with respect to which edges

6

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato

Algorithm 1: ConstructDD
N1 ← {nroot }. Ni ← ∅ for i = 2, . . . , m + 1.
for i ← 1 to m do
3
foreach n̂ ∈ Ni do
4foreach x ∈ {0, 1} do// process for the 0/1-arc
5n′ ← CheckTerminal(n̂, i, x)// Returns 0, 1, or nil.
6
if n′ = nil then// n′ is neither 0 nor 1.
′
7
Copy n̂ to n .
8UpdateInfo(n′ , i, x)
9
if there exists n′′ ∈ Ni s.t. n′′ is identical to n′ then10n′ ← n′′12else
Ni+1 ← Ni+1 ∪ {n′ }1112Create the x-arc of n̂ and make it point at n′ .

13have been selected from the root. We design the values as follows. For node n̂, let
E be the set of edges corresponding to one route from nroot to n̂ and let G be thesubgraph induced by E. We store the degree of v in G to the variable n̂.deg[v],and also store the component identifier of v to the variable n̂.comp[v], where thecomponent identifier is an integer in {1, 2, . . . , n} such that n̂.comp[v] = n̂.comp[w]if and only if v and w are in the same connected component in G (in the originalSimpath, the degree and component identifier are implicitly encoded into a single
integer named “mate”, but we describe them explicitly for generalization).
We maintain these values just for verticies incident to both a processed edge
and an unprocessed one. We call a set of these vertices frontier (Figure 3).
Morefor each i = 1,). . . , m − 1, we define the i-th frontier Fi by Fi =(∪ precisely,) (∪2 . We also define F = F
0m = ∅. For a node laj=1,...,i ej ∩j=i+1,...,m ej
beled with ei (i = 1, . . . , m), we maintain n̂.deg[v] and n̂.comp[v] for only eachvertex v in Fi−1 . Two nodes n1 and n2 labeled ei are considered as identical if
n1 .deg[v] = n2 .deg[v] and n1 .comp[v] = n2 .comp[v] for every v ∈ Fi−1 [21].
The pseudocode of UpdateInfo(n′ , i, x) is shown as Algorithm 2. It updates
n̂.deg and n̂.comp. In Line 15, we also update the component identifier in comp for
all nodes of ei as follows. For i ∈ {1, . . . , n}, let c(i) be the minimum vertex index
in the ith connected component (i.e., its component identifier is i). If the ith component does not exist, c(i) = ∞. Then, we update them so that c(1), c(2), . . . , c(n)are sorted in the ascending order. Although any node does not have the values ofn̂.deg[v] and n̂.comp[v] if v is not in the frontier, UpdateInfo works because it
references the values of n̂.deg and n̂.comp only on the frontier.
CheckTerminal(n̂, i, x) is shown as Algorithm 3. When the destination of2

In the graph theory, an edge is defined by the set∪ of vertices to which the edge is incident,i.e., ei is equivalent to, for example, {v, w}. Thus, j=1,...,i ej represents the set of vertices towhich at least one of e1 , . . . , ei is incident.

7

Frontier-based Search for Enumerating All Constrained Subgraphs

vx e
s

11

e15
vy e12 e14 e18 t
e16
e17
e20
vz e19

t

s

e13
(a)

(b)

Figure 3: Two identical states (a) and (b), in which edges in the left-hand side of dotted
oval have been processed and bold edges have been determined to use.

an arc is being decided (in Line 5-13 in Algorithm 1), if any s-t path cannot be
constructed, the destination should be 0. Considering subgraph G, once one of thefollowing conditions is satisfied, G cannot be an s-t path even if adding some edges
to G: (i-1) the degree of s or t in G exceeds 1, (i-2) a branch of the s-t path occurs(i.e., the degree of a vertex except for s and t exceeds 2) in G, and (ii) a cycle occurs
in G. In Line 2-4, we check whether (ii) holds or not. We also check whether (i-1)
and (i-2) hold or not in Line 7-11. If a vertex u is an endpoint of ei and u ̸∈ Fi , u
is no longer referred after processing ei by the definition of the frontier. Therefore,
the degree of u is fixed. In Line 12-16, we check the degree constraint of s-t path,i.e., whether the degrees of s and t are exactly one or not, and whether those of
the other vertices are zero or two, or not. If we are processing the last edge emand (i-1), (i-2) and (ii) do not hold, an s-t path has been completed (Line 18).
The UpdateInfo and CheckTerminal functions are performed locally, thatis, they do not need to traverse the DD. Our frontier-based search must inherit
this property even if it will be generalized. The computation time of them is
proportional to the number of vertices in the frontier. That of finding an identicalnode is also proportional to the frontier size if nodes are stored using a hash.
Therefore, Line 5-13 in Algorithm 1 can be executed in O(w) time, where w =maxi |Fi |. We denote the number of nodes in the constructed DD D by |D|. Hence,the computation time of Simpath is O(w · |D|), which may be exponential in ntheoretically. However, our experiments in Sec. 4 show that D often represents
O(a|D| ) s-t paths for some constant a, which indicates that the computation timeof Simpath may be significantly smaller than the number of s-t paths.

2.3

Requirements to Frontier-based Search

At the last of this section, we summarize the requirements to our frontier-based
search.
1. The frontier-based search can follow Algorithm 1 even if it is generalized,

8

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato

Algorithm 2: UpdateInfo(n̂, i, x) for Simpath
Let ei = {v, w}.
foreach u ∈ {v, w} such that u ̸∈ Fi−1 do// u is entering the frontier.
3n̂.deg[u] ← 0
4n̂.comp[u] ← j such that u = vj// The initial component identifier isthe index of u.
12

if x = 1 then// Increment the degrees of vertices v and w.
6n̂.deg[v] ← n̂.deg[v] + 1
7n̂.deg[w] ← n̂.deg[w] + 1// The two components are connected.
8cmin ← min{n̂.comp[v], n̂.comp[w]}9cmax ← max{n̂.comp[v], n̂.comp[w]}10
foreach u ∈ Fi do
11
if n̂.comp[u] = cmax then12n̂.comp[u] ← cmin
5

13
14
15

foreach u ∈ {v, w} such that u ̸∈ Fi do
Forget n̂.deg[u] and n̂.comp[u].

// u is leaving the frontier.

Renumber n̂.comp so that c(1), c(2), . . . , c(n) are sorted in the ascending order,
where c(i) is the minimum vertex v ′ satisfying n̂.comp[v ′ ] = i.

since we find that it is a common framework seen in several enumeration
algorithms using compressed representation. It is enough to generalize UpdateInfo and CheckTerminal functions
2. UpdateInfo and CheckTerminal functions have to perform their operations locally without traversing DDs. Because this is the key property thatmakes the enumeration algorithms eﬃcient.

3

Frontier-based Search for Various Subgraphs

3.1

Definition

The main reason why Simpath can quickly construct a DD is to eﬃciently decideidenticalness of nodes using the values deg and comp stored in nodes. It is important that an s-t path is a graph characterized only by the degree of each vertex andwhether having a cycle or not, and that these properties can be locally checked
during the edge selection process.
Although Simpath is designed for enumerating s-t paths, the property of s-t
path appears only in the CheckTerminal and UpdateInfo functions. Therefore, by changing the behavior of these functions we can construct DDs which
represent various subgraphs such as spanning trees and matchings as long as they
perform locally. We focus on subgraphs of Guni induced by some edge set, that is,9

Frontier-based Search for Enumerating All Constrained Subgraphs

Algorithm 3: CheckTerminal(n̂, i, x) for Simpath
Let ei = {v, w}.
if x = 1 then3
if n̂.comp[v] = n̂.comp[w] thencomponent.
4
return 0
1

2// v and w belong to the same connected// A cycle occurs (check (ii)).

Copy n̂ to n′ .
′6 UpdateInfo(n , i, x).
7 foreach u ∈ {v, w} do
8
if (u = s or u = t) and n′ .deg[u] > 1 then9
return 0
51011else if (u ̸= s and u ̸= t) and n′ .deg[u] > 2 thenreturn 0// Check (i-1).
// Check (i-2).

foreach u ∈ {v, w} such that u ̸∈ Fi do// u is leaving the frontier.
if (u = s or u = t) and n′ .deg[u] ̸= 1 then// Check (i-1).
14
return 0
12
13

15

16

else if (u ̸= s and u ̸= t) and n′ .deg[u] ̸= 0 and n′ .deg[u] ̸= 2 then(i-2).
return 0

18

if i = m thenreturn 1

19

return nil

17// Check// The processing of the last edge has been done.
// An s-t path has been completed.
// Not terminal

subgraphs G such that G = (dom(E), E) with an edge set E ⊆ Euni , where for a∪set of pairs of vertices X, dom(X) = {x,y}∈X {x, y}.
Using deg and comp, the DD representing subgraphs G of Guni specified by thefollowing properties can be constructed as same as shown in Sec. 2:(i) the degrees of each vertex in G,(ii) whether G has a cycle or not.
We make a node n̂ maintain the value n̂.cycle which represents whether graphs
correspond to n̂ have a cycle. If n̂.cycle = 1, the graphs have a cycle; otherwise(if n̂.cycle = 0) not.
In addition to the above, we can treat two properties related to connectedcomponents using comp. One is whether for each given pair of vertices (v, w), v
and w belong to the same component or not. To decide it, for a node n̂, we store
the set of vertices which is included in the connected component whose number is
x into n̂.vset[x]. Note that we store the set of only vertices that we would like to
pay attention to into n̂.vset[x]. By introducing vset, we can specify the following
property:

10

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato(iii) whether for each specified pair of vertices (v, w), v and w belong to the same
component or not.
The other is the number of connected components. Line 12 in Algorithm 3 is aconditional branch for deciding whether u is no longer incident to any unprocessededge. Then, if the connected component identifier which u belongs to is diﬀerent
from that of any vertex in the frontier Fi , there is no chance in which it is connectedwith vertices in the frontier after this moment. That is, the connected component
is decided. For a node n̂, let n̂.cc be the number of connected component. By
introducing cc, we can specify the following property:(iv) the number of connected components which G has.
Furthermore, by making a node n̂ maintain the number of edges n̂.noe, we canspecify the following:(v) the number of edges which G has.
To describe the above conditions, we define some notation for G = (dom(E), E).
We define by dG (v) the degree of v in G. If v ∈ Vuni \ dom(E), we define dG (v) = 0.
Let cG be the number of connected components in G except for isolated vertices,and qG be the 0/1-variable that represents G having a cycle or not. That is, if G
has a cycle, qG = 1; otherwise, qG = 0. The subscript of G is omitted when it isclear from the context.
We introduce the notation D, P, S, C, Q, T to formally describe the condition of(i) through (v). For every vertex v, D(v) denotes the set of possible values of dG (v).
C and Q denote the sets of possible values of cG and qG , respectively. Note thatC ⊆ {0, 1, . . . , n}. P denotes the set of vertex pairs each of which has to be includedin the same component. S denotes the set of vertex pairs each of which must not
be included in the same component. T denotes the set of possible values of thenumber of edges in G. By using the above notation, we define G(D, P, S, C, Q, T )byG(D, P, S, C, Q, T ) = {G = (dom(E), E) | E ⊆ Euni , dG (v) ∈ D(v) for each v,
cG ∈ C, qG ∈ Q, v and w are included in the same
component for each {v, w} ∈ P, x and y are included
in distinct components for each {x, y} ∈ S, |E| ∈ T }.
Let us describe our algorithm, called frontier-based search, to construct the
DD representing G(D, P, S, C, Q, T ). The framework of the method is similar to
Simpath. In particular, the pseudocode of the algorithm is the same as Algorithm 1
except for the behavior of the UpdateInfo and CheckTerminal functions. The
UpdateInfo and CheckTerminal functions for frontier-based search are shown

Frontier-based Search for Enumerating All Constrained Subgraphs

11

in Algorithm 4 and 5, respectively. The details are described as the comments inthe pseudocode.
If some of D, P, S, C, Q, T are specific values, some variables in nodes are notneeded. Specifically, if for all v ∈ Vuni , D(v) = {0, 1, . . . , n}, then we need not toremember n̂.deg. If Q = {0, 1}, P = S = ∅ and C = {0, 1, . . . , n}, then we neednot to remember n̂.comp. If P = S = ∅, then we need not to remember n̂.vset. If
C = {0, 1, . . . , n}, then we need not to remember n̂.cc. If 0 ∈ Q (i.e., we allow anacyclic graph), we need not to remember n̂.cycle. If T = {1, . . . , m}, we need not
to remember n̂.noe.
The generalized versions of UpdateInfo and CheckTerminal are still performed locally. Line 5 and 21 in Algorithm 5 need O(|S|) and O(|P |) computation time by a straightforward implementation, respectively. However, we
can reduce it to O(|Fi |) by storing pairs of the connected component identifiers{comp[v], comp[w]} for each pair in {v, w} ∈ P ∪ S into each node. Hence, thecomputation time of frontier-based search is still O(w · |D|). Note that the number of nodes in D constructed by frontier-based search may be larger than thatof nodes constructed by Simpath because more variables are stored in nodes andhence distinct nodes increase.

3.2

Several examples

In this section, we show that frontier-based search can deal with a various kind of
subgraphs by specifying D, P, S, C, Q and T in the previous section. We describe
several examples of subgraphs and how to obtain its DD by giving D, P, S, C, Q
and T .
s-t path and Hamiltonian s-t path
Although the DD representing all s-t paths can be constructed by Simpath
described in Sec. 2, we construct it also by frontier-based search shown in Sec. 3.
If D, P, S, C, Q, T are given as follows, G(D, P, S, C, Q, T ) corresponds to all thes-t paths on Guni , where s and t are vertices on Guni :• D(s) = D(t) = {1}, D(v) = {0, 2} for any v ∈ Vuni \ {s, t},• P = {{s, t}}, S = ∅,• C = {1, . . . , n},• Q = {0},• T = {1, . . . , m}.
This means that the degrees of s and t have to be one, that of all the vertices
except for s and t have to be zero or two, qG has to be zero (i.e., there is no cycle),12

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato

Algorithm 4: UpdateInfo(n̂, i, x) for frontier-based search
Let ei = {v, w}.
foreach u ∈ {v, w} such that u ̸∈ Fi−1 do// u is entering the frontier.
3n̂.deg[u] ← 0
4n̂.comp[u] ← j such that u = vj// The initial component identifier isthe index of u.
5
if u ∈ dom(P ) ∪ dom(S) then6n̂.vset[j] ← {u} such that u = vj
1

2

if x = 1 thenn̂.noe ← n̂.noe + 1// Increment the number of edges// Increment the degrees of vertices v and w.
9n̂.deg[v] ← n̂.deg[v] + 1
10n̂.deg[w] ← n̂.deg[w] + 1
11
if n̂.comp[v] = n̂.comp[w] then// A cycle is detected.
12n̂.cycle ← true
7
8

13

14
15
16
17
18

19

else
// The two components are connected.
cmin ← min{n̂.comp[v], n̂.comp[w]}cmax ← max{n̂.comp[v], n̂.comp[w]}foreach u ∈ Fi do// u is included in the next frontier.
if n̂.comp[u] = cmax thenn̂.comp[u] ← cminn̂.vset[cmin ] ← n̂.vset[cmin ] ∪ n̂.vset[cmax ]foreach u ∈ {v, w} such that u ̸∈ Fi dof ← false22
foreach z ∈ Fi do
23
if n̂.comp[u] = n̂.comp[z] then24f ← true20// u is leaving the frontier.

21

26

if f = false then// There is no vertex which belongs to the same
component as u in the next frontier.
n̂.cc ← n̂.cc + 1

27Forget n̂.deg[u] and n̂.comp[u].

2528Renumber n̂.comp so that c(1), c(2), . . . , c(n) are sorted in the ascending order,
where c(i) is the minimum vertex v ′ satisfying n̂.comp[v ′ ] = i.

and s and t have to belong to the same connected component. cG and the numberof edges can take arbitrary values, which means that the nodes in DD need not
maintain cc and noe. The variable cycle is not also needed because 1 ̸∈ Q. Eachnode maintains only variables deg and comp.
A Hamiltonian s-t path is an s-t path which includes all the vertices on Guni .
Only the degree constraints of the vertices except for s and t are diﬀerent from thecase of s-t path. That is,• D(s) = D(t) = {1}, D(v) = {2} for any v ∈ Vuni \ {s, t}.

13

Frontier-based Search for Enumerating All Constrained Subgraphs

Algorithm 5: CheckTerminal(n̂, i, x) for frontier-based search
Let ei = {v, w}.
if x = 1 then3
if 1 ̸∈ Q and n̂.comp[v] = n̂.comp[w] then// A cycle is forbidden and v
and w belongs to the same connected component.
4
return 0
1

2

5

6

if There exists {x, y} ∈ S such that x ∈ n̂.vset[n̂.comp[v]] andy ∈ n̂.vset[n̂.comp[w]] then // x and y will be in the same component.
return 0

Copy n̂ to n′ .
′8 UpdateInfo(n , i, x).
′′
9 if n .deg[v] > max{j | j ∈ D(v)} or n .deg[w] > max{j | j ∈ D(w)} thendegree of v or w exceeds all of the possible values.
10
return 0
7// Theforeach u ∈ {v, w} such that u ̸∈ Fi do// u is leaving the frontier.
if n′ .deg[u] ̸∈ D(u) then// The degree condition is not satisfied.
13
return 0
11
12

14
15
16
17

18

19

20
21

22

f ← false
foreach z ∈ Fi do
if n′ .comp[u] = n′ .comp[z] thenf ← trueif f = false then// There is no vertex which belongs to the same
component as u in the next frontier.
if n′ .cc > max{j | j ∈ C} then// The number of connectedcomponents exceeds all of the possible values.
return 0
if There exist {v ′ , v ′′ } ∈ P such that v ′ ∈ n′ .vset[n′ .comp[u]] andv ′′ ̸∈ n′ .vset[n′ .comp[u]] then // u and v ′ are in the same component,
but v ′ and v ′′ are in distinct components.
return 0

if i = m thenif n′ .cc ̸∈ C then25
return 0
23
24

26
27
28
29
30
31

32

// The processing of the last edge has been done.
// The component condition is not satisfied.

else if n′ .noe ̸∈ T thenreturn 0// Check the number of edges.

else if 0 ̸∈ Q and n′ .cycle = false thenreturn 0
else
return 1
return nil// All the constraints are satisfied.
// It is not the terminal.

14

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato

Trees and forests
A spanning tree on Guni is a subgraph of Guni such that all the vertices belong
to the same connected component and it has no cycle. If D, P, S, C, Q, T are given
as follows, G(D, P, S, C, Q, T ) corresponds to all the spanning trees on Guni :• D(v) = {1, . . . , n} for any v ∈ Vuni ,• P = {{v, w} | v, w ∈ Vuni , v ̸= w}, S = ∅,• C = {1},• Q = {0},• T = {1, . . . , m}.
This means that for any v, the degree of v is at least one, every pair of vertices
belongs to the same connected component, c(G) has to be one, and q(G) has to be
zero.
Let r1 , . . . , rℓ be vertices on Guni . A rooted spanning forest whose roots are
r1 , . . . , rℓ is a forest of Guni such that it has no cycle, the number of connectedcomponents is m, each connected component has exactly one of r1 , . . . , rℓ , and eachvertex belongs to one of m components. If D, P, S, C, Q, T are given as follows,G(D, P, S, C, Q, T ) corresponds to all the rooted spanning forests whose roots are
r1 , . . . , rℓ on Guni :• D(v) = {1, . . . , n} for any v ∈ Vuni ,• P = ∅, S = {{ri , rj } | 1 ≤ i < j ≤ ℓ},• C = {ℓ},• Q = {0},• T = {1, . . . , m}.
Let R be a set of vertices on Guni . An R-Steiner tree is a tree including all
the vertices in R. If D, P, S, C, Q, T are given as follows, G(D, P, S, C, Q, T ) corresponds to all the R-Steiner trees on Guni :• D(v) = {0, . . . , n} for any v ∈ Vuni ,• P = {{r, r′ } | r ∈ R, r′ ∈ R}, S = ∅,• C = {1},• Q = {0},• T = {1, . . . , m}.

Frontier-based Search for Enumerating All Constrained Subgraphs

15

Since on the R-Steiner tree, all the vertices in R belong to the same connectedcomponent, we specify P = {{r, r′ } | r ∈ R, r′ ∈ R}. C = {1} means that the
number of connected components has to be just one, the Steiner tree itself. Notethat since the isolated vertices should be ignored to count the number of connectedcomponents in this case, we must modify Algorithm 5 slightly (we omit the detail).
Matching
A matching on Guni is a subgraph such that the number of edges incident to eachvertex is at most one. If D, P, S, C, Q, T are given as follows, G(D, P, S, C, Q, T )corresponds to all the matchings on Guni :• D(v) = {0, 1} for any v ∈ Vuni ,• P = ∅, S = ∅,• C = {1, . . . , n},• Q = {0},• T = {1, . . . , m}.
In addition to these subgraphs, we can obtain the DD representing various
subgraphs by giving D, P, C, S, Q, T . More examples are shown in Table 1.

4

Experiments

We show that frontier-based search significantly outperforms traditional naı̈ve algorithms in enumerating spanning trees by numerical experiments. Then, we present
that the running time of frontier-based search is almost the same as that of Knuth’s
Simpath algorithm, which is dedicated for s-t path. Some other experiments werecarried out to show that frontier-based search can treat many kinds of subgraphs.
We introduce three classes of graphs Gℓ , Mℓ and Wℓ , which is given as theuniverses. Gℓ is the ℓ × ℓ grid graph. Mℓ is a graph generated from a realworld map of Nara city by the following way: First, we obtained a map near JR
Nara station from OpenStreetMap [15], and converted it to the well-known text
format using osm2wkt [10]. The well-known text format can be easily converted
to the inner format of our program. Then, we cut it so that both its width andheight are ℓ meters and JR Nara station are located at the center. We remove
all the vertices whose degree is at most two. Wℓ is a small-world graph generated
from a random small-world graph generation model, called the Watts-Strogatz
model [20], with parameter N = ℓ, K = 4 and β = 0.2. We made use of theconnected watts strogatz graph method in NetworkX library [14], which tries
to repeatedly generate a graph until connected one is obtained. The numbers of
their vertices and edges are shown in Table 2.

16

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato

Table 1: SubgraphsTypes-t path

Hamiltonian s-t path

Multiple paths

Single cycle

Multiple cycles

Hamiltonian cycle

Spanning tree

Rooted spanning forest

R-Steiner tree

Matching

Perfect matching

Edge cover

k-cliqueParameters
D(s) = D(t) = {1}, D(v) = {0, 2} for any v ∈ Vuni \ {s, t}
P = {{s, t}}, S = ∅,C = {1}, Q = {0}, T = {1, . . . , m}D(s) = D(t) = {1}, D(v) = {2} for any v ∈ Vuni \ {s, t}
P = {{v, w} | v, w ∈ Vuni , v ̸= w}, S = ∅C = {1}, Q = {0}, T = {1, . . . , m}
D(v) = {0, 1, 2} for any v ∈ Vuni ,P = ∅, S = ∅,C = {1, . . . , n}, Q = {0}, T = {1, . . . , m}
D(v) = {0, 2} for any v ∈ Vuni ,P = {{v, w} | v, w ∈ Vuni , v ̸= w}, S = ∅,C = {1}, Q = {1}, T = {1, . . . , m}
D(v) = {0, 2} for any v ∈ Vuni ,P = ∅, S = ∅,C = {1, . . . , n}, Q = {1}, T = {1, . . . , m}
D(v) = {2} for any v ∈ Vuni ,P = {{v, w} | v, w ∈ Vuni , v ̸= w}, S = ∅,C = {1}, Q = {1}, T = {1, . . . , m}
D(v) = {1, . . . , n} for any v ∈ Vuni ,P = {{v, w} | v, w ∈ Vuni , v ̸= w}, S = ∅,C = {1}, Q = {0}, T = {1, . . . , m}
D(v) = {1, . . . , n} for any v ∈ Vuni ,P = ∅, S = {{ri , rj } | 1 ≤ i < j ≤ ℓ} with roots r1 , . . . , rℓ ,C = {1, . . . , ℓ}, Q = {0}, T = {1, . . . , m}
D(v) = {1, . . . , n} for any v ∈ Vuni ,P = {{ri , rj } | ri , rj ∈ P }, Q = ∅C = {1}, Q = {0}, T = {1, . . . , m}
D(v) = {0, 1} for any v ∈ Vuni ,P = ∅, S = ∅,C = {1, . . . , n}, Q = {0}, T = {1, . . . , m}
D(v) = {1} for any v ∈ Vuni ,P = ∅, S = ∅,C = {1, . . . , n}, Q = {0}, T = {1, . . . , m}
D(v) = {1, . . . , n} for any v ∈ Vuni ,P = ∅, S = ∅,C = {1, . . . , n}, Q = {0, 1}, T = {1, . . . , m}
D(v) = {0, k − 1} for any v ∈ Vuni ,P = ∅, S = ∅,C = {1}, Q = {0, 1}, T = {k(k − 1)/2}

Frontier-based Search for Enumerating All Constrained Subgraphs

17

Table 2: Given universes and the numbers of their vertices and edges.
Graph
Gℓ
M200
M300
M400
M500
M600
M700
M800
Wℓ

# of Vertices
ℓ2
7
19
27
56
78
100
123
ℓ

# of Edges
2ℓ2 − 2ℓ
12
33
43
89
124
161
199
2ℓ

Table 3: Experiment for spanning tree. Read is the algorithm in [16].
Graph
G2
G3
G4
G5
G6
G7
G8
G9
G10
M200
M300
M400
M500
W20
W30
W40

# of
Nodes FBS
16
270
2303
15704
97265
5715763251489
18093572
99101715
629
4789
37290
343769770
44476
1198102
777244510

FBS
Time
0.00
0.01
0.01
0.02
0.03
1.06
10.00
67.06
435.35
0.01
0.02
0.02
1096.74
0.02
2.05
2186.42

Read
Time
0.00
0.01
0.184
1082.88
T/O
T/O
T/O
T/O
T/O
0.00
27.84
493.24T/O
1775.10
T/O
T/O

# of
subgraphs
4
1921003525.57568 × 108
3.25655 × 1013
1.98724 × 1019
1.26231 × 1026
8.32663 × 1033
5.69432 × 1042
392
1.76180 × 107
2.33645 × 108
2.43278 × 1018
1.10039 × 109
5.56887 × 1013
2.12187 × 1018

We implemented frontier-based search (Algorithm 1, 4 and 5) in C++, andcompiled it using g++ compiler with -O3 optimize option. The source code isavailable in https://github.com/junkawahara/frontier-experiment. All theexperiments were performed by a 2.3GHz Xeon E5-2630 computer with 128GB
memory.
We first compared frontier-based search with a conventional back-track algorithm [16] for enumerating all the spanning trees on a given universe, whose computation time is proportional to the number of solutions. The experimental results
for the cases where the universes are Gℓ , Mℓ and Wℓ for some ℓ’s are shown in
Table 3. The back-track algorithm could not count the number of the spanning
trees of G6 , which is about 3 × 1013 , whereas our algorithm succeeded in countingthat of G9 , which is about 8 × 1033 .
Secondly, we compared frontier-based search with Simpath for s-t path withthe universes Gℓ , Mℓ and Wℓ . Simpath is written in C language and compiled

18

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato

Table 4: Number of ZDD nodes, the running time and the number of solutions of frontierbased search (FBS) and Simpath for s-t path. Note that both algorithms can calculate
the exact number of solutions although it is shown as the floating point in the table.
Graph
G8
G9
G10
G11
G12
G13
G14
G15
M400
M500
M600
M700
W40
W50
W60
W70

# of
Nodes FBS
78640
274740937672314394910396094
33997610
110180128
354414745
685
2548855
6913381626023359
425755442777545
373660835
2152647207

FBS
Time
0.00
0.01
0.02
0.07
2.03
8.03
29.08
106.72
0.00
0.07
4.09
406.051.01
16.01
166.061495.73# ofNodes Simpath
64894
22414775771525198908274264
26894642
86698793
277581570
2422
1439642
14321860
851773581
2463005
40631960
185212263
2080507887

Simpath
Time
0.07
0.16
0.44
1.38
4.59
15.31
51.36
167.73
0.06
2.06
10.03
528.071.43
24.49
113.841394.71# ofsubgraphs
7.89360 × 1011
3.26660 × 1015
4.10442 × 1019
1.56876 × 1024
1.82413 × 1029
6.45280 × 1034
6.94507 × 1040
2.27450 × 1047
8288
7.17999 × 107
2.01115 × 1011
8.30693 × 1014
1.26506 × 109
1.60426 × 1011
4.21309 × 1013
6.76810 × 1015

using gcc compiler with -O3 option. In the case of Gℓ , we let the start of the paths be a corner of the grid, in the case of Mℓ , we let s be the node corresponding to
the JR Nara station, and in the case of Wℓ , we let s be a node randomly chosen.
We let the goal of the path t be the farthest node from s (if there are the two or
more farthest nodes, one of them is randomly chosen). The edges in each universe
are ordered in a breadth-first manner from s.
Table 4 shows the running times of both algorithms. This result shows that
our algorithm is comparable with Simpath; surprisingly, it is slightly faster forother than W60 and W70 . We can conclude that frontier-based search has been
generalized from Knuth’s algorithm without greatly losing the eﬃciency. Notethat since frontier-based search directly stores the values as deg and comp into
nodes, while Simpath encodes such values as “mate,” the memory requirement offrontier-based search during the computation is larger than that of Simpath.
Finally, we show the results for Hamiltonian s-t path, rooted spanning forest,
R-Steiner tree and matching. In the case of rooted spanning forest and R-Steiner
tree, we let the roots of Gℓ be the four corner vertices on the grid, and those ofMℓ and Wℓ be four nodes randomly chosen. The results are shown in Tables 5-8.
Note that these computation can be done by only changing parameters.
Each node in DD requires 16 bytes memory space to store it if we erase variablesin the node after its children have been created. Therefore, the total required
memory for constructed DD can be approximately estimated by the number ofnodes multiplied by 16.

Frontier-based Search for Enumerating All Constrained Subgraphs

19

Table 5: Experiment for Hamiltonian s-t path. Note that there is no Hamiltonian s-tpath on Gℓ when ℓ is even.
Graph
G9
G11
G13
G15
M400
M500
M600
M700
W40
W50
W60
W70

# of
Nodes FBS
103627114916911430100
117635724
351
95949
59215
26778648
2209511826601964801681
47685927

FBS
Time
0.00
0.03
3.02
39.04
0.00
0.01
0.02
30.41
0.08
7.09
75.37
130.08# ofsubgraphs
2.68830 × 109
1.44578 × 1015
1.73376 × 1022
4.62865 × 1030
60
576
12528
2140201027402.68762 × 106
3.135491 × 107
1.794379 × 108

Table 6: Experiment for rooted spanning forest.
Graph
G6
G7
G8
G9
M300
M400
M500
W20
W30

5

# of
Nodes FBS
2288711377790794677044595187
11089
92536
859422296
1065422977619

FBS
Time
0.06
3.07
25.09
172.060.02
0.03
2952.04
0.03
6.03

# of
subgraphs
2.95470 × 1015
3.59946 × 1021
4.22129 × 1028
4.84433 × 1036
2.69631 × 108
3.10111 × 1010
1.47339 × 1021
9.92928 × 1009
1.54711 × 1015

Related WorkAn algorithm for constructing the DD representing all the spanning trees has already been proposed by Sekine et al. [18], which is similar to our frontier-based
search. The purpose of their paper is not to enumerate all the spanning tree but
to compute the Tutte polynomial. However, the constructed DD for computing
the polynomial can be seen as the representation of all the spanning tree. Sekine
and Imai [17] counts the number of s-t paths in a given graph by using the DD
representing all the spanning tree and modifying it. The eﬃciency of the algorithm
is not superior to that of Simpath. Motter and Markov [13] develop an algorithm
called a compressed breadth-first search algorithm for CNF-SAT. The DD whichappears in their paper is similar to ours constructed in this paper.
In fact, we can regard the DD constructed by frontier-based search as BDDs or
Zero-suppressed BDDs (ZDDs) [11]. In [2], a general branch-and-bound algorithm
for discrete optimization is proposed. In this algorithm, the search space is represented by BDDs that the algorithm constructs. Hooker [5] considers a relation

20

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato
Table 7: Experiment for Steiner tree.
Graph
G6
G7
G8
G9
M300
M400
M500
W20
W30
W40

# of
Nodes FBS
94571
5613193213376
17952618
4672
37217
343769770
44190
1195399763758988

FBS
Time
0.04
1.06
10.02
68.03
0.01
0.02
1130.370.02
2.06
2168.72# ofsubgraphs
1.93747 × 1015
3.51350 × 1021
7.72562 × 1028
2.05461 × 1037
1.38721 × 108
4.93532 × 109
2.43278 × 1018
6.49571 × 109
8.66131 × 1014
8.31267 × 1019

Table 8: Experiment for matching.
Graph
G5
G10
G15
G20
M500
M600
M700
M800
W50
W60
W70
W80

# of
Nodes FBS
1105
17893714000121
830734329
64903
465162
10593099
565761693
662114
16154444299561
20706108

FBS
Time
0.01
0.07
82.08
9106.00
0.03
1.05
39.07
110.36
1.06
4.02
12.06
67.06

# of
subgraphs
2.81069 × 106
2.17214 × 1027
4.13975 × 1062
1.94786 × 10112
2.39934 × 1014
1.19158 × 1020
7.95097 × 1025
8.47895 × 1031
1.46547 × 1014
9.90674 × 1016
5.72795 × 1019
3.70771 × 1022

between dynamic programming and the BDDs constructed by an algorithm similar
to frontier-based search.

6

Conclusion

We have seen that frontier-based search constructs DDs representing various subgraphs by specifying the degrees of some vertices, components which some vertices
belong to, the number of components, and whether having a cycle or not. We also
have carried out some experiments to show the eﬀectiveness of our algorithm.
There are at least two another implementation on frontier-based search. One
is a Python/C++ library provided by Inoue [6], which can allow us to treat DDs
without knowing behavior of the algorithm. The other is a C++ implementation
by Iwashita et al. [8], using more advanced techniques called subsetting.
Since a DD constructed by frontier-based search satisfies requirements of ZDD,
many properties of ZDD are useful when we exploit a constructed DD. One of theFrontier-based Search for Enumerating All Constrained Subgraphs

21

most important property is that we can compute a new set from two sets by set
operations such as union and intersection using ZDDs. Using this property, it ispossible to eliminate subgraphs which do not satisfy another condition from the
DD constructed by frontier-based search (see [7] for example). We believe that our
frontier-based search can be used to solve various graph problems.

7

Acknowledgment

T. Inoue and H. Iwashita’s work was performed while they were aﬃliated with JST
ERATO, Japan.

References[1] David Avis and Komei Fukuda. Reverse search for enumeration. Discrete
Applied Mathematics, 65:21–46, 1993.
[2] David Bergman, Andre A. Cire, Willem-Jan van Hoeve, and John N. Hooker.
Discrete optimization with decision diagrams. submitted manuscript, 2013.
[3] Randal E. Bryant. Graph-based algorithms for boolean function manipulation.
IEEE Transactions on Computers, C-35(8):677–691, 1986.
[4] Gary Hardy, Corinne Lucet, and Nikolaos Limnios. A BDD-based heuristic
algorithm for design of reliable networks with minimal cost. In Jiannong Cao,Ivan Stojmenovic, Xiaohua Jia, and Sajal K. Das, editors, Mobile Ad-hoc andSensor Networks, volume 4325 of Lecture Notes in Computer Science, pages
244–255. Springer Berlin Heidelberg, 2006.
[5] John N. Hooker. Decision diagrams and dynamic programming. In Carla
Gomes and Meinolf Sellmann, editors, Integration of AI and OR Techniquesin Constraint Programming for Combinatorial Optimization Problems, volume7874 of Lecture Notes in Computer Science, pages 94–110. Springer Berlin
Heidelberg, 2013.
[6] Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato.
Graphillion: Software library designed for very large sets of graphs in Python.
Hokkaido University, Division of Computer Science, TCS Technical Reports,
TCS-TR-A-13-65, 2013.
[7] Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Koji Tsuda, Shin-ichi Minato, and Yasuhiro Hayashi.
Distribution loss minimization with guaranteed error bound. IEEE Transactions on Smart Grid, 5(1):102–111, Jan 2014.

22

Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato[8] Hiroaki Iwashita and Shin-ichi Minato. Eﬃcient top-down ZDD construction
techniques using recursive specifications. Hokkaido University, Division ofComputer Science, TCS Technical Reports, TCS-TR-A-13-69, 2013.
[9] Donald E. Knuth. The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1. Addison-Wesley Professional, 1st edition, March
2011.
[10] Christoph P. Mayer.
osm2wkt - openstreetmap to wkt conversion.
http://www.tm.kit.edu/ mayer/osm2wkt, 2010.
[11] Shin-ichi Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proceedings of the 30th ACM/IEEE Design Automation
Conference, pages 272–277, 1993.
[12] Shin-ichi Minato, Takeaki Uno, and Hiroki Arimura. LCM over ZBDDs: Fast
generation of very large-scale frequent itemsets using a compact graph-based
representation. In Takashi Washio, Einoshin Suzuki, Kai Ming Ting, andAkihiro Inokuchi, editors, Advances in Knowledge Discovery and Data Mining,volume 5012 of Lecture Notes in Computer Science, pages 234–246. Springer
Berlin Heidelberg, 2008.
[13] DoRon B. Motter and Igor L. Markov. A compressed breadth-first search forsatisfiability. In David M. Mount and Cliﬀord Stein, editors, Algorithm Engineering and Experiments, volume 2409 of Lecture Notes in Computer Science,
pages 29–42. Springer Berlin Heidelberg, 2002.
[14] NetworkX developer team. NetworkX. https://networkx.github.io/
documentation/latest/index.html.
[15] OpenStreetMap
contributors.
http://www.openstreetmap.org.

OpenStreetMap.

[16] Robert. C. Read and Robert. E. Tarjan. Bounds on backtrack algorithms forlisting cycles, paths, and spanning trees. Networks, 5:237–252, 1975.
[17] Kyoko Sekine and Hiroshi Imai. Counting the number of paths in a graph via
BDDs (special section on discrete mathematics and its applications). IEICE
transactions on fundamentals of electronics, communications and computersciences, 80(4):682–688, 1997-04-25.
[18] Kyoko Sekine, Hiroshi Imai, and Seiichiro Tani. Computing the Tutte polynomial of a graph of moderate size. In Proceedings of the 6th International
Symposium on Algorithms and Computation (ISAAC), pages 224–233, 1995.
[19] Shuji Tsukiyama, Isao Shirakawa, Hiroshi Ozaki, and Hiromu Ariyoshi. An
algorithm to enumerate all cutsets of a graph in linear time per cutset. J.
ACM, 27(4):619–632, October 1980.

Frontier-based Search for Enumerating All Constrained Subgraphs

23[20] Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ’small-world’
networks. Nature, 393:440–442, 1998.
[21] Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki
Iwashita, and Shin-ichi Minato. Finding all solutions and instances of numberlink and slitherlink by ZDDs. Algorithms, 5(2):176–213, 2012.