Tree Decomposition-based Approach for Compiling Independent Sets
-
- Sugaya Teruji
- Graduate School of Information Science and Technology, Hokkaido University
-
- Nishino Masaaki
- NTT Communication Science Laboratories, NTT Corporation
-
- Yasuda Norihito
- NTT Communication Science Laboratories, NTT Corporation
-
- Minato Shin-ichi
- Graduate School of Informatics, Kyoto University
Abstract
<p>Knowledge compilation is a method for compiling a knowledge base into an appropriate data structure, generally called tractable language. Graph substructure plays an important role in knowledge compilation and frontier-based search is known to be an efficient algorithm, in which computation time is bounded by the path-width of a graph. For some limited classes of graph structures, studies have shown that it can be improved and bounded by the branch-width, however, the redesign of an algorithm for other classes does not appear to be straightforward. In this paper, we focus on the similarity between frontier-based search and dynamic programming on tree decomposition. Dynamic programming on tree decomposition has been intensely studied for varieties of problems on counting or optimization of graph substructures. However, to the best of our knowledge, they are rarely applied to knowledge compilation. Then, we show that dynamic programming for finding the size of the maximum independent set can be, by simple replacement, applied to the compilation of independent sets. Furthermore, we empirically show that our method can compile much faster than conventional frontier-based search in some instances, and it becomes several orders of magnitude faster especially when the tree-width is small compared to the path-width.</p>
Journal
-
- Journal of Information Processing
-
Journal of Information Processing 28 (0), 354-368, 2020
Information Processing Society of Japan
- Tweet
Details 詳細情報について
-
- CRID
- 1390003825198228352
-
- NII Article ID
- 130007873364
-
- ISSN
- 18826652
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed