Project: HyperTrac: Hypergraph Decompositions and Tractability
(funded by the Austrian Science Fund (FWF) under grant P30930)
Contents
Top
Project team
Project leader
Project staff
- Julia Theresa Csar
- Wolfgang Fischl
- Markus Kroell
- Matthias Lanzinger
- Davide Longo
- Cem Okulmus
- Reinhard Pichler
- Igor Razgon
- Stefano Sferrazza
- Sebastian Skritek
Project partners
TopGoal of the Project
Answering Conjunctive Queries (CQs) as well as solving Constraint Satisfaction Problems (CSPs) are fundamental tasks in Computer Science. Due to their inherent complexity (they are classical NP-complete problems), the search for tractable fragments of these problems has been an active research area for many years. Hypertree decompositions (HDs) and their generalizations to generalized hypertree decompositions (GHDs) and fractional hypertree decompositions (FHDs) allow us to define the widest tractable classes of CQs and CSPs known to date. These techniques have been successfully applied to CSP solving and have meanwhile also been integrated into commercial database systems.
However, the computation of an appropriate HD, GHD, or FHD is itself a demanding problem. Algorithms for this task exist, but they do not scale: The complexity of computing an optimal HD or deciding if an HD of a given width exists increases exponentially with the width of the given CQ or CSP. We have recently shown that the problems of deciding if a GHD or FHD of a given width exists are NP-complete even for width 2. Therefore, intensive further research on algorithms for computing HDs, GHDs, and FHDs is required.
In this project, we will tackle the problem of computing HDs, GHDs, and FHDs both from a theoretical and practical point of view. For HDs, we aim at new algorithmic approaches to reduce the exponential dependency on the width. For GHDs and FHDs, we aim at identifying natural classes of CQs and CSPs for which the computation of a GHD or FHD of desired width is tractable. From a theoretical perspective, our goal is thus an improvement of worst-case complexity bounds. From a practical perspective, our goal is the development and implementation of algorithms that work well on real-world problem instances.
Duration
The project has officially started on 2018-06-01 and has a duration of four years.
Publications
- The HyperTrac Project: Recent Progress and Future Research Directions on Hypergraph Decompositions In CPAIOR, pages 3-21, Springer, Lecture Notes in Computer Science 12296, 2020.
[ BibTeX ] - Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems In IJCAI, pages 1726-1733, ijcai.org, 2020.
[ BibTeX ] - Semantic Width Revisited (Extended Abstract) In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
[ BibTeX ] - Fast and Parallel Decomposition of Constraint Satisfaction Problems In IJCAI, pages 1155-1162, ijcai.org, 2020.
[ BibTeX ] - Parallel Computation of Generalized Hypertree Decompositions In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
[ BibTeX ] - HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings In PODS, pages 464-480, ACM, 2019.
[ BibTeX ] - HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
[ BibTeX ] - On the Enumeration Complexity of Unions of Conjunctive Queries In PODS, pages 134-148, ACM, 2019.
[ BibTeX ] - A complexity theory for hard enumeration problems In Discret. Appl. Math., 268: 191-209, 2019.
[ BibTeX ] - Complexity Bounds for Relational Algebra over Document Spanners In PODS, pages 320-334, ACM, 2019.
[ BibTeX ] - Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection In Theory Comput. Syst., 65 (1): 3-41, 2021.
[ BibTeX ] - Towards Reconciling Certain Answers and SPARQL: Bag Semantics to the Rescue? In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
[ BibTeX ] - On the Language of Nested Tuple Generating Dependencies In ACM Trans. Database Syst., 45 (2): 8:1-8:59, 2020.
[ BibTeX ] - Datalog: Bag Semantics via Set Semantics In ICDT, pages 16:1-16:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, LIPIcs 127, 2019.
[ BibTeX ]