AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Compiling Graph Substructures into Sentential Decision Diagrams
Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, Masaaki Nagata

Last modified: 2017-02-12

Abstract


The Zero-suppressed Sentential Decision Diagram (ZSDD) is a recentlydiscovered tractable representation of Boolean functions. ZSDD subsumes theZero-suppressed Binary Decision Diagram (ZDD) as a strict subset, andsimilar to ZDD, it can perform several useful operations like model countingand Apply operations. We propose a top-down compilation algorithmfor ZSDD that represents sets of specific graph substructures, e.g.,matchings and simple paths of a graph. We experimentally confirm that theproposed algorithm is faster than other construction methods includingbottom-up methods and top-down methods for ZDDs, and the resulting ZSDDsare smaller than ZDDs representing the same graph substructures. We alsoshow that the size constructed ZSDDs can be bounded by the branch-width of thegraph. This bound is tighter than that of ZDDs.

Keywords


Knowledge Compilation, Propositional Knowledge Base, Graph, Sentential Decision Diagrams

Full Text: PDF