TCS -TR-A-16-80

TCS Technical Report

Acceleration of ZDD Construction for Subgraph
Enumeration via Path-width OptimizationbyYuma Inoue and Shin-ichi Minato

Division of Computer Science
Report Series A
October 14, 2016

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-6469

Fax:+81-011-706-6469

Acceleration of ZDD Construction for Subgraph
Enumeration via Path-width Optimization
Yuma Inoue

Shin-ichi Minato

Division of Computer Science
Graduate School of Info. Sci. and Tech.
Hokkaido University
Sapporo 060-0814, Japan

Division of Computer Science
Graduate School of Info. Sci. and Tech.
Hokkaido University
Sapporo 060-0814, Japan

October 14, 2016

Abstract
Many graph problems require us to find subgraphs satisfying constraints
such as no cycle, connected, degree-bounded and so on. Frontier-based search
is a framework to construct a compressed data structure ZDD storing all subgraphs satisfying constraints in a given graph. Since frontier-based search
processes edges one by one in a given order, we should determine an edge
order of a given graph as input for frontier-based search. The performanceof frontier-based search, including the size of a constructed ZDD, deeply depends on what edge order is given. In this paper we propose a meta-heuristic
algorithm to determine a good edge order for frontier-based search. Since thisordering problem is related to minimum path-width problem, our method canalso be considered as a method for minimum path-width problem. Experimental results show our method is useful for both of frontier-based search andminimum path-width problem.

1

Introduction

Graph is one of important discrete structure on both of theoretical and practicalareas of computer science. Many graph problems ask us to find “one” solutionthat is optimal under some evaluation function. On the other hand, there are a
few results to find “all” solutions and store them, because practically the numberof solutions is huge, exponential to graph size in the worst case. However, if westore all solutions, we can analyze and manipulate them much more: counting,random sampling, extraction with criteria, and of course optimization.
Frontier-based search [11] is one of frameworks to enumerate all subgraphs ofa given graph with constraints. Frontier-based search constructs a compresseddata structure ZDD [14] storing all solutions. Not only compactness of ZDD may
enable us to store all solutions, but also ZDD has set algebra operations that can be1

2

Yuma Inoue and Shin-ichi Minato

applied without restoring. Therefore, taking intersection of two ZDDs, counting thenumber of solutions, and finding the optimal solution are done in time depending
only on the size of ZDDs, not on the number of solutions. Frontier-based search has
been used in several applications such as path enumeration [10], power network [7],and puzzle game [19].
Our goal in this paper is to improve the eﬃciency of frontier-based search inorder to apply frontier-based search to as large graphs as possible. To achieve thisgoal, we focus on edge ordering of a graph. To use frontier-based search, we should
give an edge order to the method as input. The performance of the method andthe size of a resulting ZDD are dramatically aﬀected by the edge order. Details
will be discussed in Section 3.
Furthermore, we indicate the relation between frontier-based search and a wellknown graph parameter path-width in section 3.4, though it is known as a folklore.
This means our problem is NP-complete as well as minimum path-width problem.
We thus propose meta-heuristics to find a good edge order for frontier-based search.
Our algorithm can also be considered as a method to find a path decomposition
with small path-width.
We propose our ordering algorithm in Section 4. Our algorithm is based onbeam search with multiple start vertices found by linear time heuristic search.
The features of our algorithm are:• practical: Most previous algorithms focus on only maximum path-width. But
complexity of frontier-based search is aﬀected by entire width. Our algorithm
consciously evaluates the average width too.
• scalable: frontier-based search runs in linear time to graph size but in exponential time to path-width. Thus main targets of frontier-based search
are not so large graphs with small path-width, and we should obtain enoughsmall width for such graphs. Our algorithm runs in O(|V ||E|K), where V isa vertex set, E is an edge set, K is a user-selected parameter. Hence it will
work on graphs with |V |, |E| ≤ 10,000 in feasible time.
In Section 5, we give experimental results to evaluate the practical performanceof our algorithm. Results show our method achieves to find a good path decomposition in terms of both of the maximum and average width. Results also indicate
there is a significant improvement of frontier-based search on many instances byusing our method.

2

Graph and Subgraph Enumeration

Our problem is to improve the eﬃciency of frontier-based search, which is analgorithm to construct data structure storing all restricted subgraphs. Before introduction of frontier-based search, we briefly review subgraph enumeration withcompressed data structure in this section.

Acceleration of ZDD Construction for Subgraph Enumeration via Path-width Optimization

2.1

3Graph Notation

Let G = (V, E) be an undirected graph G with a vertex set V and an edge set E ⊆{{u, v} | u, v ∈ V }. We set n = |V | and m = |E|. We denote neighbors for a vertex∪
v by N (v) = {u | {u, v} ∈ E}, and for a vertex set S by N (S) = v∈S N (v) \ S.
We say an undirected graph G′ = (V ′ , E ′ ) is a subgraph of G = (V, E) if V ′ ⊆ V
and E ′ ⊆ E.

2.2

Subgraph Enumeration

Subgraph enumeration is enumeration of all subgraphs satisfying given constraints,
such as no cycle, connected, degree bounded, and so on. For example, if a given
constraint forces there is no cycle in subgraph, we should enumerate all subgraphsthat are forests.
Since the number of subgraphs can be huge, in the worst case 2m , listing all
subgraphs may be impractical. An idea to overcome this combinatorial explosion
is using compressed data structure for subgraphs.

2.3

ZDD

Zero-suppressed Decision Diagram (ZDD) [14] is data structure derived from Binary Decision Diagram (BDD) [2] to represent sets of combinations. Because asubgraph in a graph can be represented as a combination of edges1 , we can also
use a ZDD to represent a set of subgraphs in a graph.
A ZDD is a directed acyclic graph (DAG) that is obtained by reducing a binary
decision tree. A binary decision tree consists of five types of components: internal
nodes, 0-edges, 1-edges, the ⊥-sink, and the ⊤-sink. Each internal node is labeledwith an edge-id, and has exactly two out-going edges: a 0-edge and a 1-edge. Eachpath from a root to the ⊤-sink corresponds to a subgraph; if a 1-edge originatesfrom a node with label e, the subgraph contains e, while a 0-edge means that the
subgraph does not contain e.
The following two rules reduce a binary decision tree to a ZDD, which is acompact and canonical form:• sharing rule: share all nodes which have the same labels and child nodes.
• deleting rule: delete all nodes whose 1-edge points to the ⊥-sink.
Figure 1 shows an example of a reduced ZDD representing all restricted subgraphs
in a given graph.
Once we get a ZDD, several operations can be used to analyze and manipulate
subgraphs in the ZDD. For example, counting the number of subgraphs and finding
1

if we do not matter isolate vertices

4Yuma Inoue and Shin-ichi Minato

a
c
d e

b

0

b

f
a
c

a

b

c

c

a

b

d

d e

d

e
c
b

1

e

d
f

f

e
f
⊤

Figure 1: A ZDD representing all K3 in K4 , where Kn denote a complete graphwith n vertices. Note that a ZDD has exactly one ⊥-sink basically; we illustrate
multiple ⊥’s for visibility.

the smallest sum of edge-weights of subgraphs correspond to counting the numberof paths and computing the shortest path in a DAG, which are solved in linear time.
Moreover, there are intersection and union operations between two ZDDs, whose
computation time theoretically bounded by the product of the size of two ZDDs,
not depends on the cardinality. Here, the size of a ZDD means the number of nodes
in a ZDD. Thus, eﬃcient compression by ZDD encourages not only preventing
combinatorial explosion but also fast computation after ZDD construction.
In order to obtain a ZDD from a binary decision tree, we should fix an edge
order; if an edge a is numbered smaller than b, a must be higher than b in a binary
decision tree. Using diﬀerent edge orders changes ZDD structure, and aﬀects thecompression ratio of ZDD. Details of relation between edge orders and ZDD size
will be discussed in the next section.

3

Frontier-based search and Problem DefinitionZDD helps enumeration of huge number of subgraphs and analysis of them. But if
we construct a ZDD by listing all subgraphs, we indeed cannot avoid exponential
calculation time. Frontier-based search is a ZDD construction framework without
trying all possibility.

3.1

Algorithm Overview

Frontier-based search [11] is a ZDD construction framework. Basically, frontierbased search constructs a binary decision tree in top-down manner, deleting andsharing redundant ZDD nodes. Thus, how to delete and share the nodes is thecore of the algorithm.
To identify redundant nodes, we store “state” for each ZDD node. Stored information in states depends on given constraints for subgraphs. For example, suppose
we enumerate forests. Then the information in states is connections between pairs

Acceleration of ZDD Construction for Subgraph Enumeration via Path-width Optimization

6

b

1

a
2

5
3

c
4
used

d
e

f
7
8

6

b

1

a
2

g

5
3

c
4

9
unused

d
e

5

f
7
8

g

9

unprocessed

Figure 2: Equivalent states in the middle of frontier-based search to enumerate all
sub-forests.

of vertices. If we add e = {u, v} to a current state (i.e. use 1-edge in a ZDD) andu and v are already connected in the current state, this is invalid because it makes
cycle(s). Therefore, we connect the node with the current state to the ⊥-sink with
1-edge. Moreover, if two ZDD nodes have the same state (e.g. same connections in
the forest case), valid edge selections are also same. Hence we can share the nodes
with the same state. Note that a ZDD made by frontier-based search may not
be well-reduced. We should use a reduction algorithm after frontier-based search,which runs in linear time to the size of a non-reduced ZDD.
In the state, we have to consider only a subset of V , called frontier, not all
vertices in V . A frontier is a set of the vertices which are adjacent to both of theprocessed edges and the unprocessed edges. More formally, a frontier Fi of the∪∪i-th level is defined by Fi = 1≤j≤i ej ∩ i+1≤k≤m ek , if we use the edge order
e1 , . . . , em . Figure 2 illustrates an example of frontiers of the 5-th level. Again,
suppose we enumerate forests. Then we can consider two subgraphs in figure 2
have the same state, because b and d are connected but e is not connected with band d in both of the subgraphs.
To enumerate subgraphs with other constraints, we should define the state andthe pruning rules for each problem. The paper [11] provides a problem list withthe state and the pruning rules that can be solved by the frontier-based searchframework.

3.2

Our Problem

Our goal is to improve the performance of frontier-based search in order to analyze
and manipulate restricted subgraphs eﬃciently. There are several ways aﬀecting
the performance of frontier-based search: changing state definition, adding sophisticated pruning rules, using an appropriate edge order.
In this paper, we focus on edge ordering to accelerate frontier-based searchbecause:• The other techniques cannot be considered separately from given constraints.
The best edge order may depend on given constraints too, but we can determine an edge order only from a given graph. This is important for intersection

6

Yuma Inoue and Shin-ichi Minato

of multiple ZDDs with diﬀerent constraints, since intersection operation canbe used for two ZDDs with the same order.
• Although a ZDD made by frontier-based search can be diﬀerent by using
the other techniques, after reducing, the ZDD will be same because a fully
reduced ZDD has a canonical form unless changing the edge order. Edgeordering is only a way aﬀecting the size of the reduced ZDD.
Hence, our problem in this paper is to determine a good edge order only from agiven graph such that the order makes frontier-based search faster and the resulting
ZDD smaller.

3.3

Theoretical Analysis

To improve the performance of frontier-based search, we should deeply understandwhat factors essentially aﬀect the performance. Time complexity of frontier-based
search is bounded by the number of states and the size of states. For example, astate for enumeration of sub-forests is connected components between the vertices
in each frontier F . Thus, the number of states in the level i is bounded by the
number of set partitions of a frontier Fi , which is known as Bell number B|Fi | . The
size of states, i.e. the size of information to distinguish it from other states, isalso bounded by O(log B|Fi | ). Hence the time complexity of frontier-based search∑
to enumerate all sub-forests is bounded by O( mi=1 log B|Fi | B|Fi | ). On the other∑m
hand, the size of a ZDD is O( i=1 B|Fi | ), because a ZDD has not to store state
information after construction.
∑
In general, the complexity of frontier-based search is bounded by O( mi=1 f (|Fi |)),
where f (x) is a function determined by state definition, and exponential to x inmany problems. Thus, it is natural that we guess a good edge order will yieldsmall frontiers.

3.4

Frontier-based search and Path Decomposition

The definition of frontier for edge ordering is almost same as vertex separator for
vertex ordering. The j-th vertex separator Sj on the vertex order v1 , . . . , vn isdefined as Sj = {vi | i ≤ j, ∃k > j, {vi , vk } ∈ E}. We assume the edge order
e1 , . . . , em such that for ex = {vi , vj } (i < j) and ey = {vk , vl } (k < l), x < y
if j < l. Then frontier Fx with ex = {vi , vj } (i < j) satisfies Fx ⊆ Sj−1 ∪ {vj }.
∪It is because 1≤i≤x ei = {v1 , . . . , vj } holds and vk (k < j) is in Fx if vk has atleast one unprocessed edge, which is {vk , vl } (k < j ≤ l), and thus vk satisfies
the definition of vertex separator Sj−1 . Furthermore, ex adds only vj to Sj−1 , notadds vi because vi is already in Sj−1 due to {vi , vj }. Therefore, |Fx | ≤ |Sj−1 | + 1
holds when we use the above edge order. Relation between vertex separators and afrontier-based search on BDD, similar data structure to ZDD, has been discussed
in [17], for example.

Acceleration of ZDD Construction for Subgraph Enumeration via Path-width Optimization

7

Furthermore, it is known that the maximum size of vertex separators is equivalent to the path-width of a corresponding path decomposition [12]. Path decomposition of G = (V, E) is a sequence (X1 , . . . Xl ) of subsets of V , called bags, satisfying
the following requirements:• For each edge e = {u, v} ∈ E, there is at least one bag Xi such that u, v ∈ Xi .
• For each vertex v ∈ V , if there are two bags Xi , Xj (i < j) both of whichcontain v, for all i ≤ k ≤ j, Xk also contains v.
Path-width of a path decomposition is the maximum size max1≤i≤l |Xi | of bags.
Therefore, a path decomposition with small path-width seems to yield a goodvertex order for a good edge order.
In the context, frontier-based search can be considered as a dynamic programming (DP) algorithm on a path decomposition. But we purposely use frontierbased search rather than DP on a path decomposition for subgraph enumeration
problems because:• We can consider a non-reduced ZDD made by frontier-based search is equivalent to a DP table of a path decomposition. Thus, the reduced ZDD has
smaller size than a DP table, which will accelerate DP calculation (i.e. traversal of the DAG). This is a merit especially when we repeatedly computediﬀerent objective functions and edge-weights dynamically change.
• If there are multiple constraints, designing DP on a path decomposition may
be complex. ZDD framework makes it easy by constructing ZDDs for eachconstraints respectively and taking ZDD intersection operations. Moreover,
we can also use subsetting technique [9], which can compute intersections
maybe faster than ordinary intersection operation.

4

Proposed Method

A path decomposition with small path-width will yield a good vertex order for agood edge order to frontier-based search. We review previous work to computesmall path-width before proceeding our method.

4.1

Previous Work for Path Decomposition

Lengauer [13] shows computing the minimum of the maximum vertex separator
is NP-complete problem, and Kinnersley [12] shows this problem is equivalent tofinding the minimum path-width. Therefore, two goals have been mainly discussed
in the literature: (1) computing the exact optimal width as fast as possible and(2) computing as a good solution as possible within feasible time by heuristics.

8

Yuma Inoue and Shin-ichi Minato

For exact solution, there are several results about polynomial time algorithms
for restricted graph classes. [16, 1, 5, 18] For general graphs, Coudert et al. [3]proposed an algorithm based on branch and bound. The paper [3] shows thisalgorithm faster than SAT-based algorithm in most cases.
As heuristics, several linear time algorithms have been proposed such as:• DFS/BFS [15]: Vertices are ordered by the traversal order of depth-first/breadthfirst search.
• NDS [15]: For the order v1 , . . . , vi−1 , let S = {v1 , . . . , vi−1 }. Then a vertexv ∈ V \ S with maximum |N (v) ∩ S| is chosen as the next vertex vi .
• LUD [4]: For the order v1 , . . . , vi−1 , let S = {v1 , . . . , vi−1 }. Then a vertexv ∈ V \ S with maximum |N (v) ∩ S| − |N (v) ∩ (V \ S)| is chosen as the next
vertex vi .
These heuristics must choose a start vertex (typically, with the smallest degree).
Many researches using frontier-based search use BFS ordering as input. For instance, Graphillion package [6], which is a library using frontier-based search, supports DFS/BFS ordering and sets BFS ordering as default.
On the other hand, Duarte et al. [4] proposed a meta-heuristic algorithm basedon basic variable neighborhood search (BVNS). BVNS repeats local search withrandom shake of current optimal solution within time limit explicitly set by users.
BVNS uses the evaluation function such that the smaller number of large bags ishighly evaluated, thus we can consider BVNS decreases not only the maximum
size but also the entire size.

4.2

Overview of Proposed Method

We propose an algorithm for computing a path decomposition with small pathwidth. Moreover, we focus on improving “practical” performance of frontier-based
search. Namely,• Practically, we guess the graph size can be dealt by frontier-based search
is n, m ≤ 10,000 and path-width up to 20 from the theoretical complexity.
Thus, algorithms should be polynomial time. On the other hand, linear time
seems to be too fast; we can compute further to improve the quality.
• Typical path-width optimization focuses on minimizing the maximum width.
∑
But complexity of frontier-based search is O( mi=1 f (|Fi |)). Thus, we should
also care about the entire size of frontiers, not only the maximum one.
Our algorithm consists of three parts:
1. Calculate appropriate start vertices by using linear time heuristics.

Acceleration of ZDD Construction for Subgraph Enumeration via Path-width Optimization

9

2. Calculate a good vertex order by using beam search with appropriate startvertices.
3. Calculate a good edge order from a calculated good vertex order.
We first introduce the core of our algorithm, beam search, in the next subsection. Since preliminary experiment shows the performance of beam search deeply
depends on a start vertex, we also propose a strategy to choose appropriate startvertices. Finally, we propose an edge ordering algorithm to obtain a better edge
order from a vertex order.

4.3

Core Algorithm: Beam Search

We use beam search to compute a good vertex order. Beam search is a searchalgorithm pruning search space with evaluation function. Beam search traverses
search space in breadth-first manner and expand only K states with top-K evaluation score in the same search level. Here, K, called beam width, is a parameter
given by users.
The i-th step of our beam search determine the i-th vertex as follows: We
already have K orders, each of which consists of i − 1 vertices. For each order, we
try to add a vertex that is adjacent to at least one vertex in the current frontier.
Here we obtain a new list of orders consisting of i vertices. Then we extract top-K
orders with evaluation function, and proceed next i + 1-th step. Our algorithm
finally outputs the most highly evaluated order in the n-th step.
∑
We use the sum of the squares of frontier sizes ik=1 |Fk |2 as evaluation function
for the i-th step, where smaller values are considered highly evaluated. This is for
decreasing the maximum frontier size and average frontier size simultaneously. In
the tiebreak case, we use another evaluation function |N (Fi ) ∩ (V \ {v1 , . . . , vi−1 })|,
smaller is highly evaluated too. This is because (1) the set of neighbors may becomea future frontier and (2) decreasing candidates helps to reduce expansion of search
space, i.e. save runtime.
The time complexity of this algorithm is O(n(mK + nK log K)): The algorithm
examines K search nodes n times. Each expansion yields at most n search nodes,
and updates evaluation functions for each added vertex v in O(|N (v)|) time. Thus
each expansion costs O(m) time in total. Now, we have at most nK search nodes.
We sequentially add these nodes to a heap keeping provisional top-K nodes, whose
maintenance cost is O(log K) per one node, and finally the K next search nodes
are in the heap.

4.4

Improvement by Using New Light Search Algorithm: RFS

Preliminary experiments indicate the performance of beam search deeply depends
on a start vertex, and sometime beam search without fixing a start vertex misses

10Yuma Inoue and Shin-ichi Minato

an appropriate start vertex since small beam width forces beam search to select astart vertex from the information about only few vertices around it. Therefore, wechoose likely appropriate vertices by another way and try them as start vertices.
In order to get appropriate vertices, we use linear time heuristics. We can run
linear time algorithm n times for our target graph size. Thus we evaluate eachvertex in terms of the maximum and average frontier size of the result of heuristic
search using it as a start vertex. Top-L vertices are chosen as appropriate vertices
for beam search; then we run beam search L times with L start vertices respectively
and output optimal one among the L results.
To improve the quality more, we also propose a new linear time heuristics RFS:
For the order v1 , . . . , vi−1 , let S = {v1 , . . . , vi−1 }. First, we choose v ∈ S withminimum |N (v) ∩ (V \ S)|.2 Then a vertex u ∈ N (v) ∩ (V \ S) with minimum|N (u) ∩ (V \ S)| is chosen as the next vertex. This intends to choose a vertex thatlooks like to be easily removed from the current frontier to keep frontier size small.
Experimental results shown in Section 5.3 suggest RFS is the best heuristic
search for many instances. Hence we use RFS to calculate appropriate start vertices
for beam search.
Another advantage by using good heuristics is we can also use the best resultof the heuristics as our optimal solution, if it is better than a beam search result.
The good performance of RFS is also useful in terms of using its results directly.

4.5

Computing Edge Order via Vertex Order

Now, we can obtain a vertex order by the algorithm in previous subsections. In
the next step, we should transform it to an edge order. In Section 3.4, we haveseen the edge ordering such that |Fx | ≤ |Sj−1 | + 1 holds. But this ordering can be
improved in terms of entire frontier size.
If we fix a vertex order, the frontier transitions are uniquely determined as shownin figure 3. Here, each vertex v has an interval in the frontier transition such thatv is added to a frontier and v is removed from a frontier. This can be examinedby the correspondence between frontiers and bags of a path decomposition.
A key idea is edge e = {u, v} can be processed at any time in the interval that is
the intersection of the intervals of u and v. We use edge e at the minimum frontierin the valid interval described above. This cause reduction of entire frontier size
since for each edge, the size of the frontier in which the edge is processed is lessthan or equal to the original size.

2

but it must be greater than 0; N (v) ∩ (V \ S) = ϕ means v is not in frontier.

Acceleration of ZDD Construction for Subgraph Enumeration via Path-width Optimization

2

2

1

2

1
3

4

1
3

5

11

4

3

5

4
5

2

2

1

1
3

4

3

5

4
5

2
3

Figure 3: Frontier transitions and vertex intervals.

5

Experimental Results

5.1

Experiment Environment

We conducted computational experiments to evaluate our algorithm and comparewith previous work. All algorithms are implemented in C++ with g++ 4.9.3
compiler. We also use TdZdd library [8] to implement frontier-based search. We
carried out experiments on a 3.20 GHz CPU machine with 64 GB memory.
We use two graph datasets: Rome Graph and VSPLIB. Rome Graph is road
networks used as benchmark in [3]. We use 140 graphs with n = 100, 119 ≤ m ≤158. VSPLIB is used as benchmark for vertex separation problem in [4]. We use
73 instances of HB from VSPLIB, which come from the Harwell-Boeing Sparse
Matrix Collection. Graphs in VSPLIB have 24 ≤ n ≤ 960 and 46 ≤ m ≤ 7442.

5.2

Performance of Edge Ordering

We first show results for the edge ordering algorithm in Section 4.5. Here, we use
vertex orders generated by RFS. Table 1 presents experimental results.
Our edge ordering strategy achieves to reduce the maximum frontier size by
one in almost a half of instances. Furthermore, average frontier size also decreases
about 2 % in Rome Graph and 4 % in VSPLIB. An important fact is our proposed
algorithm does not increase the maximum and average frontier size, as shown inthe minimum of the diﬀerence. Hereafter, we thus use this algorithm to obtain anedge order from vertex order.

5.3

Path Decomposition by Linear Time Heuristics

We next compare linear time heuristics, where a start vertex is fixed to a vertex
with the minimum degree. Table 2 describes experimental results.
Our RFS is the best in terms of both of the maximum and average frontier size.
Especially for Rome Graph dataset, RFS is the best in almost all cases. Thus we12

Yuma Inoue and Shin-ichi Minato

Table 1: Comparing edge ordering algorithms: naı̈ve ordering (in Section 3.4) v.s.
proposed ordering (in Section 4.5).
max frontier size
#improved instances
Rome
VSPLIB

63
44

average frontier size
diﬀ: naı̈ve−proposed
ratio: naı̈ve/proposed
averageminmax averageminmax
0.152 0.065 0.346
1.019 1.007 1.038
0.868 0.000 9.466
1.043 1.000 1.277

Table 2: Comparing linear time heuristics: previous algorithms (in Section 4.1)
v.s. proposed algorithm (in Section 4.4). “#best” means the number of instances
for which a corresponding method can compute the best frontier size among listed
algorithms. “ave. diﬀ.” means the average of the diﬀerences between the frontier
size computed by a corresponding method and the best size for each instance.

Rome
VSPLIB#best
ave. diﬀ.
#bestave. diﬀ.

DFS
0
7.78
5
38.42

max frontier size
BFS NDS LUD
0
1
5
7.99
7.11
4.14
22
9
21
8.33 19.37 10.11

RFS
137
0.02
47
4.25

DFS
0
4.63
4
21.13

average frontier size
BFS NDS LUD
0
0
4
4.71
4.40
2.48
21
4
13
4.19 10.86
5.10

use RFS as linear time heuristics to determine start vertices for beam search. BFS
and LUD are second best, and if we merge the results of these three algorithms,
we achieve to get the best ordering among heuristics in almost all cases including
VSPLIB.

5.4

Path Decomposition by Meta-heuristics

We evaluate the performance of our beam search in terms of frontier size. We
compare our algorithm with BFS, which is usually used in frontier-based search,
and BVNS-based method in [4] with 1000 seconds time limit. We fix a beam width
K = 5000 and the number of start vertices L = 10. Our algorithm runs in 0.64
to 787.59 seconds, which depends on the size of each graph. Table 3 describes
experimental results.
Our algorithm achieves to get the best size for about 80% instances in bothdatasets. Furthermore, even in the case our algorithm misses the best, it finds
an order enough close to the best, as shown in the average diﬀerence. On theother hand, BFS seems not to be a sophisticated ordering for path decomposition.
Averagely, the diﬀerence of maximum frontier size between BFS ordering and thebest is more than 10, which may exponentially aﬀect the performance of frontierbased method.

RFS
136
0.01
42
2.35

Acceleration of ZDD Construction for Subgraph Enumeration via Path-width Optimization

13

Table 3: Comparing BFS, BVNS (in Section 4.1), and beam search (in Section 4.2).
“#best” and “ave. diﬀ.” mean same as ones in Table 2.

Rome
VSPLIB#best
ave. diﬀ.
#bestave. diﬀ.

max frontier size
BFS BVNS beam
087
120
10.7070.421 0.150
123963
11.781
3.795 0.685

average frontier size
BFS BVNS beam
0
22
118
6.296
0.401 0.027
4
23
58
5.714
2.097 0.419

Table 4: Relation between the maximum frontier size and the number of the instances for which a ZDD is constructed. “#in time” means the number of instances
for which frontier-based search runs in time limit 1000 seconds. “#timeout” means
the number of instances for which frontier-based search exceed the time limit.
BFS
max frontier size
Total
≤ 11 12 13 14 15 16 17 ≤#in time
0
0
2
1
3
0
0
6
Rome
#timeout
0
0
0
3
1
5
125
134
#in time
14
3
0
0
1
1
0
19
VSPLIB#timeout
0
1
0
0
0
0
53
54
BVNS
beam
max frontier size
max frontier size
Total
Total
≤ 10 11 12 13 ≤≤ 11 12 13 ≤#in time
87 29
7
0
123
121
4
0
125
Rome
#timeout
0
0
8
9
17
0
7
8
15
#in time
19
2
1
0
22
24
1
0
25
VSPLIB#timeout
0
1
0
50
51
0
1
47
48

5.5

Eﬃciency of Frontier-based search with Path Decompositionbased Ordering

Finally, we evaluate the impact of our algorithm to apply frontier-based search.
In this experiment, we enumerate all sub-forests in a given graph and construct a
ZDD for them with time limit 1000 seconds.
Table4 shows the relation between the maximum frontier size F and the solvability of frontier-based search for all sub-forests. The total number of solved
instances by BFS ordering are really less than the ones by meta-heuristics, especially in Rome Graph. This shows the ordering based on a path decompositionis eﬀective to improve the performance of frontier-based search. Both of metaheuristic methods can construct a ZDD for all F ≤ 10 cases and cannot constructa ZDD for all F ≥ 13 cases. On the other hand, BFS sometime constructs a ZDD
up to F ≤ 16 cases. This result is interesting and may be the key to improve ouralgorithm, but we have not revealed the details yet.
Table 5 summarizes the performance of frontier-based search using path decompositionbased ordering. Before the comparison between our method and BVNS, we notice

14

Yuma Inoue and Shin-ichi Minato

Table 5: Comparing the performance of frontier-based search using an edge orderby meta-heuristics: BVNS (in Section 4.1) v.s. beam search (in Section 4.2).
“average” means the average of results for instances for which both ordering canconstruct a ZDD (i.e. 119 instances for Rome Graph and 22 instances for VSPLIB).
“#best” means the number of instances for which the best result is obtained by acorresponding ordering. “#2-folds” means the number of instances for which theresult of a corresponding ordering is twice or more better than the other ordering.

Rome

VSPLIBaverage#best#2-folds
average#best#2-folds

runtime
BVNS
beam
35.81 s 32.68 s
63
66
23
39
41.11 s 25.30 s
10
15
1
8

non-reduced ZDD size
BVNS
beam
140,496,029 129,300,247
60
69
21
38
135,520,389
83,321,337
10
12
0
5

reduced ZDD size
BVNS
beam
11,542,286 11,010,751
63
66
16
32
22,976,532 14,510,650
9
12
0
5

the impact of the reduction of ZDDs. On the average, reduced ZDDs are morecompact than non-reduced ones about 11 times in Rome Graph instances and 6
times in VSPLIB. This means dynamic programming on a path decomposition canbe accelerated 6 to 11 times after ZDD reduction.
In 140 Rome Graph instances, ZDDs for 4 instances are constructed only by
BVNS ordering, ZDDs for 6 instances are constructed only by beam search ordering, and 119 instances are constructed by both ordering. In 73 VSPLIB instances,
ZDDs for 0 instances are constructed only by BVNS ordering, ZDDs for 3 instances
are constructed only by beam search ordering, and 22 instances are constructed byboth orderings.
The results of the averages and the number of the best looks like there is no
big diﬀerence in our method and BVNS. We guess this is because BVNS also
decreases the entire size by the evaluation function. On the other hand, we canfind meaningful diﬀerences in the cases with the ratio is twice or more, i.e. there issignificant improvement, especially in VSPLIB. Figure 4 illustrates details of thefact. In many cases, the two methods show close performance. But the number of
meaningful improvements by our method is more than the one by BVNS.

6Conclusion

To improve frontier-based search, we focus on the edge ordering because it is robust
to change constraints and aﬀects not only runtime but also the size of a resulting
ZDD. We propose meta-heuristic algorithm that find small frontier size, using
relation between frontiers and path decomposition.
Our algorithm can find a good path decomposition in terms of both of the
maximum and average bag size in the decomposition. Moreover, our algorithm
achieves to construct ZDDs for many instances for which the standard ordering BFS

Acceleration of ZDD Construction for Subgraph Enumeration via Path-width Optimization

12

beam search
BVNS

60

the number of instances

the number of instances

70

50
40
30
20
10
0

15

beam search
BVNS

10
8
6
4
2
0

0

2
4
6
8 10 12 14 16 18
ratio of ZDD size comparing with the other(a) Rome Graph

20

0

2
4
6
8 10 12 14 16 18
ratio of ZDD size comparing with the other20(b) VSPLIB

Figure 4: The number of instances with the ratio of reduced ZDD size comparing
with the other method.

cannot construct ZDDs. Our algorithm also tends to reduce runtime of frontierbased search and the size of a resulting ZDD compared with the previous pathdecomposition method BVNS. On the other hand, the performance of frontierbased search using an edge order by our algorithm is frequently worse than the one
by BVNS even in the case our algorithm yields a better path decomposition than
BVNS in terms of the size of frontiers. Our future work is to reveal the key factorof this phenomenon for further improvement of frontier-based search.
Acknowledgements. This work was partially supported by JST ERATO
Minato Project, and JSPS KAKENHI 15H05711 and 15J01665. We are indebted
to Hirofumi Suzuki for providing implementation of frontier-based search to enumerate all sub-forests using TdZdd library.

References[1] Hans L. Bodlaender, Ton Kloks, and Dieter Kratsch. Treewidth and pathwidthof permutation graphs. SIAM Journal on Discrete Mathematics, 8(4):606–616,
1995.
[2] Randal E. Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, C-35(8):677–691.
[3] David Coudert, Dorian Mazauric, and Nicolas Nisse. Experimental evaluationof a branch and bound algorithm for computing pathwidth. In Proceedingsof the 13th International Symposium of Experimental Algorithms (SEA2014),
pages 46–58, 2014.
[4] Abraham Duarte, Laureano F. Escudero, Rafael Mart, Nenad Mladenovic,
Juan Jos Pantrigo, and Jess Snchez-Oro. Variable neighborhood search for thevertex separation problem. Computers & Operations Research, 39(12):3247 –
3255, 2012.

16

Yuma Inoue and Shin-ichi Minato[5] Jens Gusted. On the pathwidth of chordal graphs. Discrete Applied Mathematics, 45(3):233–248, 1993.
[6] Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato.
Graphillion: software library for very large sets of labeled graphs. International Journal on Software Tools for Technology Transfer, 18(1):57–66, 2014.
[7] Takeru Inoue, Kyoya Takano, Toshio Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Kazuhiko Tsuda, Shin-ichi Minato, and Yasuhiro
Hayashi. Distribution loss minimization with guaranteed error bound. IEEE
Transactions on Smart Grid, 5(1):102–111, 2014.
[8] Hiroaki Iwashita. TdZdd. URL: https://github.com/kunisura/TdZdd.
[9] Hiroaki Iwashita and Shin-ichi Minato. Eﬃcient top-down ZDD construction
techniques using recursive specifications. TCS technical report TCS-TR-A13-69, Division of Computer Science, Hokkaido University, 2013.
[10] Hiroaki Iwashita, Yoshio Nakazawa, Jun Kawahara, Takeaki Uno, and Shinichi Minato. Eﬃcient computation of the number of paths in a grid graphwith minimal perfect hash functions. TCS technical report TCS-TR-A-10-64,
Division of Computer Science, Hokkaido University, 2013.
[11] Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, and Shin-ichi Minato.
Frontier-based search for enumerating all constrained subgraphs with compressed representation. TCS technical report TCS-TR-A-14-76, Division ofComputer Science, Hokkaido University, 2014.
[12] Nancy G Kinnersley. The vertex separation number of a graph equals its
path-width. Information Processing Letters, 42(6):345–350, 1992.
[13] Thomas Lengauer. Black-white pebbles and graph separation. Acta Informatica, 16(4):465–475, 1981.
[14] Shin-ichi Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In proceedings of the 30th Design Automation Conference(DAC1993), pages 272–277, 1993.
[15] Yuchang Mo, Liudong Xing, Farong Zhong, Zhusheng Pan, and Zhongyu
Chen. Choosing a heuristic and root node for edge ordering in BDD-based network reliability analysis. Reliability Engineering & System Safety, 131:83–93,
2014.
[16] Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, andChuan Yi Tang. A linear-time algorithm for constructing an optimal nodesearch strategy of a tree. In Proceedings of the 4th Annual International
Computing and Combinatorics Conference (COCOON1998), pages 279–289,
1998.

Acceleration of ZDD Construction for Subgraph Enumeration via Path-width Optimization

17[17] Kyoko Sekine and Hiroshi Imai. Counting the number of paths in a graph via
BDDs. IEICE transactions on fundamentals of electronics, communications
and computer sciences, 80(4):682–688, 1997.
[18] Karol Suchan and Ioan Todinca. Pathwidth of circular-arc graphs. In Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in
Computer Science (WG2007), pages 258–269, 2007.
[19] 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, 2012.