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

Winner of the Marco Cadoli Best Student Paper Award 2020

2020-10

We are pleased to announce that team member Markus Hecher won the prestigious Marco Cadoli Best Student Paper Award at KR 2020. A detailed news report in German can be found at the website of TU Wien. Marco Cadoli Best Student Paper Award 2020

Co-Organization of ASPOCP 2020

2020-07

The 13th edition of the Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2020) will be co-organized by project member Markus Hecher. Information of the workshop is available at the ASPOCP 2020 website.

CP 2020 and KR 2020: Accepted Papers

2020-07

We are grateful to announce that in total we got three accepted papers for CP 2020. Further, our work entitled "Treewidth-Aware Reductions of normal ASP to SAT – Is normal ASP harder than SAT after all?" got accepted for publication at the KR conference in Rhodes.

Co-Organization of MC 2020 and MCW 2020

2020-07

We are delighted to report that the first international competition on model counting (MC 2020) as well as the first international workshop on model counting (MCW 2020) were a success! Details of the results can be found online at mccompetition.org. Both events were co-organized by project member Markus Hecher.

LICS 2020 and SAT 2020: Published Papers

2020-07

We gladly announce that our recent study on Lower Bounds for QBFs of Bounded Treewidth got accepted for publication at the virtual conference LICS 2020. Further, we were able to present our work on "Taming High Treewidth with Abstraction, Nested Dynamic Programming, and Database Technology" at the SAT 2020 conference.

Recent Journal Publications

2020-07

We are proud to announce that this project resulted in two recent journal publications. Both works "Complexity of abstract argumentation under a claim-centric view" and "Solving Advanced Argumentation Problems with Answer Set Programming" provide new insights for abstract argumentation.

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 October 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. Markus Hecher Treewidth-aware Reductions of Normal ASP to SAT - Is Normal ASP Harder than SAT after All? In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020), pages 485-495, 2020.
    [ BibTeX | doi  ]
  2. Johannes Klaus Fichte, Markus Hecher and Stefan Szeider A Time Leap Challenge for SAT-Solving In Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings, Volume 12333 of Lecture Notes in Computer Science, pages 267-285, Springer, 2020.
    [ BibTeX | doi  ]
  3. Johannes Klaus Fichte, Markus Hecher and Stefan Szeider Breaking Symmetries with RootClique and LexTopSort In Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings, Volume 12333 of Lecture Notes in Computer Science, pages 286-303, Springer, 2020.
    [ BibTeX | doi  ]
  4. Johannes Klaus Fichte, Markus Hecher and Maximilian F. I. Kieler Treewidth-Aware Quantifier Elimination and Expansion for QCSP In Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings, Volume 12333 of Lecture Notes in Computer Science, pages 248-266, Springer, 2020.
    [ BibTeX | doi  ]
  5. Manuel Bichler, Michael Morak and Stefan Woltran selp: A Single-Shot Epistemic Logic Program Solver In Theory Pract. Log. Program., 20 (4): 435-455, 2020.
    [ BibTeX | doi  ]
  6. Johannes Klaus Fichte, Markus Hecher and Andreas Pfandler Lower Bounds for QBFs of Bounded Treewidth In LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020, pages 410-424, 2020.
    [ BibTeX | doi  ]
  7. Markus Hecher, Patrick Thier and Stefan Woltran Taming High Treewidth with Abstraction, Nested Dynamic Programming, and Database Technology In Theory and Applications of Satisfiability Testing - SAT 2020 - 23rd International Conference, Alghero, Italy, July 3-10, 2020, Proceedings, pages 343-360, 2020.
    [ BibTeX | doi  ]
  8. Gerhard Brewka, Martin Diller, Georg Heissenberger, Thomas Linsbichler and Stefan Woltran Solving Advanced Argumentation Problems with Answer Set Programming In Theory Pract. Log. Program., 20 (3): 391-431, 2020.
    [ BibTeX | doi  ]
  9. Wolfgang Dvorák and Stefan Woltran Complexity of abstract argumentation under a claim-centric view In Artif. Intell., 285: 103290, 2020.
    [ BibTeX | doi  ]
  10. Bernhard Bliem, Michael Morak, Marius Moldovan and Stefan Woltran The Impact of Treewidth on Grounding and Solving of Answer Set Programs In J. Artif. Intell. Res., 67: 35-80, 2020.
    [ BibTeX | doi  ]
  11. 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 ]
  12. 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-10-07 20:19

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