[2N5-OS-17b] OS-17 (2)

[2N5-OS-17b-03] Construction of BDD for Indexing Vertex Separators between All Vertex Pairs of Graphs

〇Masahiro Takahashi¹, Jun Kawahara¹, Shin-ichi Minato¹ (1. Graduate School of Informatics, Kyoto University)

Keywords:decision diagram, enumeration, graph algorithm

It is fundamental to consider vertex separators of a given graph. In this article, we propose an algorithm that, when an undirected graph is given as input, indexes all vertex separators of all vertex pairs in a form that can be easily used later. In this article, we first formulate the indexing of vertex separators as a dynamic programming problem. Then by using a data structure called BDD for indexing, we aim for an efficient algorithm. In the experiments, the proposed algorithm was applied to square lattice graphs, which are graphs with a regular structure, and randomly generated graphs. As a result, it was found that the proposed algorithm operates fast especially on graphs with regular structures and graphs with dense edges. We also show that by slightly changing the details of the proposed algorithm, it is possible to index vertex sets similar to vertex separators, such as those which cause d-separation in Bayesian networks.