Skip to Content

TU Wien Fakultät für Informatik DBAI Database and Artificial Intelligence Group
Top-level Navigation: Current-level Navigation:

Path: DBAI > Research > Projects > Hypar Project

Tools: Print


Project: HYPAR - Hybrid Parameterized Problem Solving in Practice

FWF
(funded by the Austrian Science Fund (FWF) under grant P 32830)

Contents


News

Research Visit in Bergen

2020-02

We were able to pay our project partner Jan Arne Telle and Martin Vatshelle a visit in Bergen. Thanks for the fruitful cooperation! Our Visit of Martin Vatshelle and Jan Arne Telle in Bergen

AAAI 2020: Accepted Papers

2020-01

We are delighted to announce that our work on Structural Decompositions of Epistemic Logic Programs has been accepted for presentation at this year's AAAI conference in New York.

Project started

2019-10

The project officially started on Octobe 1, 2019 and will have a duration of three years.

Top

Goal of the Project

Solving computationally hard problems is a key challenge in computer science. One approach towards efficient solutions relies on decomposing the problem instances into smaller parts and solving the problem step-by-step by solving parts (subproblems) via a dedicated algorithm. This dedicated algorithm then suitably combines solutions of the single parts into a solution of the problem. One particular form of this method is known as dynamic programming over tree decompositions. The runtime of this approach mainly depends on a certain parameter, namely the size of the largest subproblem, which can be obtained via tree decompositions satisfying certain criteria. The common hypothesis for this approach is that the smaller the parts obtained by the decomposition are, the faster the problem at hand can be solved. However, practical experiments have shown that this theoretical rule of thumb does not necessarily apply in practice.

Our working hypothesis is that decompositions with larger subproblems might be beneficial in practice, in particular if dedicated algorithms are used to solve subproblems. Therefore, we call this approach hybrid since it relies on both standard approaches for the subproblems and the dedicated dynamic programming machinery for combining solutions to subproblems. In this project, we aim to better understand which "shapes" of decompositions provide the best results in practice, and to study methods on how to find these decompositions. In the course of the project, we will focus on several prominent problems in computer science, ranging from Boolean satisfiability (SAT) and extensions thereof, Satisfiability on Quantified Boolean Formulas (QSAT) as well as Answer Set Programming (ASP, also known as disjunctive datalog).

Top

Project Team

Project leader

Project staff

Former staff

National project partners

International project partners

Top

Systems and Tools

Systems delivered and extended in course of the project are publicly available.

Software

Top

Publications

Here, we provide a list of all project publications.

2020

  1. Johannes Klaus Fichte, Markus Hecher, Patrick Thier and Stefan Woltran Exploiting Database Management Systems and Treewidth for Counting In 22nd Symposium on Practical Aspects of Declarative Languages (PADL), Volume 12007 of Lecture Notes in Computer Science, pages 151-167, Springer, 2020.
    [ BibTeX ]
  2. Markus Hecher, Michael Morak and Stefan Woltran Structural Decompositions of Epistemic Logic Programs In 34th AAAI Conference on Artificial Intelligence (AAAI), 2020.
    [ BibTeX ]
Top
Last updated: 2020-03-24 12:48

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. Disclaimer / Datenschutzerklärung