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

Accepted Papers at CP and KR

2021-10

We are happy to announce that two papers by team members have been accepted to this year's International Conference on Principles and Practice of Constraint Programming (CP 2021) and another two papers (one long, one short) at the International Conference on Principles of Knowledge Representation and Reasoning (KR 2021).

Best Paper Awards at ICLP'21

2021-09
Best Paper at ICLP'21

We are pleased to announce that team members Viktor Besin and Markus Hecher and PI Stefan Woltran won the Best Paper Award and Best Student Paper Award with their paper Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs at the International Conference on Logic Programming ICLP 2021.

Bachelor and Master Theses of Team Members

2021-04

Team member Viktor Besin successfully defended his bachelor thesis, and team member Matthias König successfully defended his master thesis.
Congratulations!

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

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.

2021

  1. Viktor Besin, Markus Hecher and Stefan Woltran Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs In Theory and Practice of Logic Programming, 21 (5): 575-592, 2021.
    [ BibTeX | doi  ]
  2. Wolfgang Dvořák, Matthias König and Stefan Woltran On the Complexity of Preferred Semantics in Argumentation Frameworks with Bounded Cycle Length In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, November 3-12, 2021, pages 671-675, 2021.
    [ BibTeX | doi  ]
  3. Thomas Eiter, Markus Hecher and Rafael Kiesel Treewidth-Aware Cycle Breaking for Algebraic Answer Set Counting In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, November 3-12, 2021, pages 269-279, 2021.
    [ BibTeX | doi  ]
  4. Thomas Eiter, Markus Hecher and Rafael Kiesel aspmc: An Algebraic Answer Set Counter In Proceedings of the International Conference on Logic Programming 2021 Workshops co-located with the 37th International Conference on Logic Programming (ICLP 2021), Porto, Portugal (virtual), September 20th-21st, 2021, Volume 2970 of CEUR Workshop Proceedings, CEUR-WS.org, 2021.
    [ BibTeX ]
  5. Johannes Klaus Fichte, Markus Hecher and Valentin Roland Parallel Model Counting with CUDA: Algorithm Engineering for Efficient Hardware Utilization In 27th International Conference on Principles and Practice of Constraint Programming, CP 2021, Montpellier, France (Virtual Conference), October 25-29, 2021, Volume 210 of LIPIcs, pages 24:1-24:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
    [ BibTeX | doi  ]
  6. Johannes Klaus Fichte, Markus Hecher, Ciaran McCreesh and Anas Shahab Complications for Computational Experiments from Modern Processors In 27th International Conference on Principles and Practice of Constraint Programming, CP 2021, Montpellier, France (Virtual Conference), October 25-29, 2021, Volume 210 of LIPIcs, pages 25:1-25:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
    [ BibTeX | doi  ]
  7. Johannes Klaus Fichte, Markus Hecher, Yasir Mahmood and Arne Meier Decomposition-Guided Reductions for Argumentation and Treewidth In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 1880-1886, ijcai.org, 2021.
    [ BibTeX | doi  ]
  8. Johannes Klaus Fichte, Markus Hecher and Arne Meier Knowledge-Base Degrees of Inconsistency: Complexity and Counting In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 6349-6357, AAAI Press, 2021.
    [ BibTeX ]
  9. Jorge Fandinno and Markus Hecher Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 6312-6320, AAAI Press, 2021.
    [ BibTeX ]
  10. Wolfgang Dvořák, Alexander Gressler, Anna Rapberger and Stefan Woltran The Complexity Landscape of Claim-Augmented Argumentation Frameworks In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 6296-6303, AAAI Press, 2021.
    [ BibTeX ]
  11. Johannes Klaus Fichte, Markus Hecher, Michael Morak and Stefan Woltran DynASP2.5: Dynamic Programming on Tree Decompositions in Action In Algorithms, 14 (3): 81, 2021.
    [ BibTeX | doi  ]
  12. Wolfgang Dvořák, Matthias König and Stefan Woltran Graph-Classes of Argumentation Frameworks with Collective Attacks In Logics in Artificial Intelligence - 17th European Conference, JELIA 2021, Virtual Event, May 17-20, 2021, Proceedings, Volume 12678 of Lecture Notes in Computer Science, pages 3-17, Springer, 2021.
    [ BibTeX | doi  ]

2020

  1. Johannes Klaus Fichte, Markus Hecher and André Schidler Solving the Steiner Tree Problem with few Terminals In 32nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2020, Baltimore, MD, USA, November 9-11, 2020, pages 293-300, IEEE, 2020.
    [ BibTeX | doi  ]
  2. Manuel Bichler, Michael Morak and Stefan Woltran lpopt: A Rule Optimization Tool for Answer Set Programming In Fundam. Informaticae, 177 (3-4): 275-296, 2020.
    [ BibTeX | doi  ]
  3. Stefan Woltran Computational Argumentation - Formal Models and Complexity Results (invited talk) In Proceedings of the 35th Italian Conference on Computational Logic - CILC 2020, Rende, Italy, October 13-15, 2020, Volume 2710 of CEUR Workshop Proceedings, pages 2, CEUR-WS.org, 2020.
    [ BibTeX ]
  4. 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  ]
  5. 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  ]
  6. 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  ]
  7. 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  ]
  8. 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  ]
  9. 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  ]
  10. 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  ]
  11. 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  ]
  12. Wolfgang Dvořák and Stefan Woltran Complexity of abstract argumentation under a claim-centric view In Artif. Intell., 285: 103290, 2020.
    [ BibTeX | doi  ]
  13. 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  ]
  14. 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 ]
  15. Markus Hecher, Michael Morak and Stefan Woltran Structural Decompositions of Epistemic Logic Programs In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 2830-2837, AAAI Press, 2020.
    [ BibTeX ]
Top
Last updated: 2021-10-19 17:31

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