Fast and parallel decomposition of constraint satisfaction problems

被引：0
作者：
Georg Gottlob
Cem Okulmus
Reinhard Pichler
机构：
[1] University of Oxford,
[2] TU Wien,undefined
来源：
Constraints | 2022年 / 27卷
关键词：
Constraint satisfaction; Hypergraphs; Structural decomposition methods; Parallel computing;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Constraint Satisfaction Problems (CSP) are notoriously hard. Consequently, powerful decomposition methods have been developed to overcome this complexity. However, this poses the challenge of actually computing such a decomposition for a given CSP instance, and previous algorithms have shown their limitations in doing so. In this paper, we present a number of key algorithmic improvements and parallelisation techniques to compute so-called Generalized Hypertree Decompositions (GHDs) faster. We thus advance the ability to compute optimal (i.e., minimal-width) GHDs for a significantly wider range of CSP instances on modern machines. This lays the foundation for more systems and applications in evaluating CSPs and related problems (such as Conjunctive Query answering) based on their structural properties.
引用
收藏
页码：284 / 326
页数：42
相关论文
共 37 条
[1]  
Adler I(2007)Hypertree width and related hypergraph invariants European Journal of Combinatorics 28 2167-2181
[2]  
Gottlob G(2016)A compressed generalized hypertree decomposition-based solving technique for non-binary constraint satisfaction problems AI Comm. 29 371-392
[3]  
Grohe M(1996)A linear-time algorithm for finding tree-decompositions of small treewidth SIAM J. Comput. 25 1305-1317
[4]  
Amroun K(2008)A unified theory of structural tractability for constraint satisfaction problems Journal of Computer and System Sciences 74 721-743
[5]  
Habbas Z(1983)Degrees of acyclicity for hypergraphs and relational database schemes J. ACM 30 514-550
[6]  
Aggoune-mtalaa W(1962)Algorithm 97: Shortest path Communications of the ACM 5 345-282
[7]  
Bodlaender HL(2000)A comparison of structural CSP decomposition methods Artificial Intelligence 124 243-627
[8]  
Cohen DA(2002)Hypertree decompositions and tractable queries Journal of Computer and System Sciences 64 579-30:32
[9]  
Jeavons P(2009)Generalized hypertree decompositions: NP-hardness and tractable variants J. ACM 56 30:1-4:20
[10]  
Gyssens M(2014)Constraint solving via fractional edge covers ACM Trans. Algorithms 11 4:1-89
1234