Fast parallel hypertree decompositions in logarithmic recursion depth

Conference item

Various classic reasoning problems with natural hypergraph representations are known to be tractable when a hypertree decomposition (HD) of low width exists. The resulting algorithms are attractive for practical use in fields like databases and constraint satisfaction. However, algorithmic use of HDs relies on the difficult task of first computing a decomposition of the hypergraph underlying a given problem instance, which is then used to guide the algorithm for this particular instance. The performance of purely sequential methods for computing HDs is inherently limited, yet the problem is, theoretically, amenable to parallelisation.

In this paper we propose the first algorithm for computing hypertree decompositions that is well-suited for parallelisation. The newly proposed algorithm log-k-decomp requires only a logarithmic number of recursion levels and additionally allows for highly parallelised pruning of the search space by restriction to so-called balanced separators. We provide a detailed experimental evaluation over the HyperBench benchmark and demonstrate that log-k-decomp outperforms the current state-of-the-art significantly.

Authors: Gottlob, G; Lanzinger, M; Okulmus, C; Pichler, R

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Host title: PODS '22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
• Pages: 325–336
• Publication date: 2022-06-13
• Acceptance date: 2022-02-28
• Event title: ACM Symposium on Principles of Database Systems (PODS 2022)
• Event location: Philadelphia, PA, USA
• Event website: https://2022.sigmod.org/index.shtml
• Event start date: 2022-06-12
• Event end date: 2022-06-17
• DOI: 10.1145/3517804.3524153
• ISBN: 9781450392600
• Language: English
• Keywords: hypertree width; hypergraph decomposition; FFR; parallel algorithms