The Bag-Based Search: A Meta-Algorithm to Construct Tractable Logical Circuits for Graphs Based on Tree Decomposition

Tractable logical circuits (TLCs) have attracted more attention in the AI field as bases of knowledge representation and tractable probabilistic modeling. We propose the bag-based search (BBS), a new meta-algorithm for constructing a TLC that accepts all subgraphs of a given input graph that satisfies a target graph property. We implemented BBS examples for various graph properties, including independent set, k-edgeset, dominating set, k-matchings, and spanning trees, and applied them to artificial and real-world graphs. The experimental results showed that BBS generated significantly smaller circuits than ZDDs obtained by the frontier-based search (FBS).