Project: HyperTrac: Hypergraph Decompositions and Tractability
(funded by the Austrian Science Fund (FWF) under grant P30930)
Top
Project leader
Project staff
Project partners
Top
Goal 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.
Top
Publications
- Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus and Reinhard Pichler 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 ] - Hubie Chen, Georg Gottlob, Matthias Lanzinger and Reinhard Pichler Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems In IJCAI, pages 1726-1733, ijcai.org, 2020.
[ BibTeX ] - Georg Gottlob, Matthias Lanzinger and Reinhard Pichler Semantic Width Revisited (Extended Abstract) In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
[ BibTeX ] - Georg Gottlob, Cem Okulmus and Reinhard Pichler Fast and Parallel Decomposition of Constraint Satisfaction Problems In IJCAI, pages 1155-1162, ijcai.org, 2020.
[ BibTeX ] - Georg Gottlob, Cem Okulmus and Reinhard Pichler Parallel Computation of Generalized Hypertree Decompositions In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
[ BibTeX ] - Wolfgang Fischl, Georg Gottlob, Davide Mario Longo and Reinhard Pichler HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings In PODS, pages 464-480, ACM, 2019.
[ BibTeX ] - Wolfgang Fischl, Georg Gottlob, Davide M. Longo and Reinhard Pichler HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
[ BibTeX ] - Nofar Carmeli and Markus Kröll On the Enumeration Complexity of Unions of Conjunctive Queries In PODS, pages 134-148, ACM, 2019.
[ BibTeX ] - Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek and Heribert Vollmer A complexity theory for hard enumeration problems In Discret. Appl. Math., 268: 191-209, 2019.
[ BibTeX ] - Liat Peterfreund, Dominik D. Freydenberger, Benny Kimelfeld and Markus Kröll Complexity Bounds for Relational Algebra over Document Spanners In PODS, pages 320-334, ACM, 2019.
[ BibTeX ] - Stefan Mengel and Sebastian Skritek Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection In Theory Comput. Syst., 65 (1): 3-41, 2021.
[ BibTeX ] - Sebastian Skritek Towards Reconciling Certain Answers and SPARQL: Bag Semantics to the Rescue? In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
[ BibTeX ] - Phokion G. Kolaitis, Reinhard Pichler, Emanuel Sallinger and Vadim Savenkov On the Language of Nested Tuple Generating Dependencies In ACM Trans. Database Syst., 45 (2): 8:1-8:59, 2020.
[ BibTeX ] - Leopoldo E. Bertossi, Georg Gottlob and Reinhard Pichler Datalog: Bag Semantics via Set Semantics In ICDT, pages 16:1-16:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, LIPIcs 127, 2019.
[ BibTeX ]
Top
Last updated: 2021-03-18 15:30