The HyperTrac Project: Recent Progress and Future Research Directions on Hypergraph Decompositions
This paper addresses the challenge of making NP-complete CSPs tractable for researchers and practitioners in AI and Operations Research, but it is an incremental review of existing work.
This paper reviews recent advancements and outlines future research directions in hypergraph decompositions, which are used to identify tractable fragments of NP-complete Constraint Satisfaction Problems (CSPs). The focus is on the computational challenges associated with these decompositions themselves.
Constraint Satisfaction Problems (CSPs) play a central role in many applications in Artificial Intelligence and Operations Research. In general, solving CSPs is NP-complete. The structure of CSPs is best described by hypergraphs. Therefore, various forms of hypergraph decompositions have been proposed in the literature to identify tractable fragments of CSPs. However, also the computation of a concrete hypergraph decomposition is a challenging task in itself. In this paper, we report on recent progress in the study of hypergraph decompositions and we outline several directions for future research.