Fast Compilation of s-t Paths on a Graph for Counting and Enumeration

[edit]

Norihito Yasuda, Teruji Sugaya, Shin-Ichi Minato ;
Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, PMLR 73:129-140, 2017.

Abstract

In this paper, we propose a new method to compile $s$-$t$ simple paths on a graph using a new compilation method called merging frontier based search. Recently, Nishino et al. proposed a top-down construction algorithm, which compiles $s$-$t$ simple paths into a Zero-suppressed SDD (ZSDD), and they showed that this method is more efficient than simpath by Knuth. However, since the method of Nishino et al. uses ZSDD as a tractable representation, it requires complicated steps for compilation. In this paper, we propose z-st-d-DNNF, which is a super set of ZSDD. By using this method instead of ZSDD, we show that more efficient $s$-$t$ simple paths compilation can be realized.

Related Material