TCS-TR-A-16-80

Date: Fri Oct 14 19:44:04 2016

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

Authors: Yuma Inoue and Shin-ichi Minato

Contact:

First name: Shin-ichi
Last name: Minato
Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060- 0814, Japan
Email: minato@ist.hokudai.ac.jp

Abstract. Many graph problems require us to nd 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 performance of 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 this ordering problem is related to minimum path-width problem, our method can also be considered as a method for minimum path-width problem. Experimental results show our method is useful for both of frontier-based search and minimum path-width problem.