Treating Hard Problems with Decomposition and Dynamic Programming
(funded by the Austrian Science Fund (FWF) under grant Y698)
Contents
News
Project ended
2022-09 The project ended at 31.05.2022.Recent Awards for Markus Hecher
2022-09Recently, Markus Hecher has won the EurAI dissertation award 2021, as well as the GI Dissertationspreis 2021 for his excellent PhD thesis. Further, for his contributions in KR and AI so far, he received the KR Early Career Award 2022.
Erwin Schrödinger Research Funding
2022-03An Erwin Schrödinger Research Funding was granted to team member Markus Hecher. He will work on his project "QuantASP - Quantitatives Schlussfolgern und Zählen für ASP" (translation: quantitative reasoning and counting for ASP) at the "Computer Science and Artificial Intelligence Laboratory" at M.I.T. (Massachusetts Institute of Technology).
Dissertation Awards for PhD theses
2021-12For their respective dissertations, Jan Maly received the "Dissertationspreis der Stadt Wien" from the city council of Vienna, and Markus Hecher received the "award of excellence" from the Austrian ministry of education, science, and research. You can find out more about the awardees and their theses here.
Accepted Papers at CP and KR
2021-10We 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
We are pleased to announce that Viktor Besin, 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.
Successful Argumentation Solvers at ICCMA
2021-08
The project team submitted two argumentation solvers to this year's International Competition on Computational Models of Argumentation (ICCMA): the new tree decomposition-based portfolio A-Folio DPDB and the updated ASP-based ASPARTIX-V21 system.
We are happy to announce that A-Folio DPDB won the classical tracks for complete and stable semantics, and ASPARTIX-V21 won the classical track for stage semantics!
Special Issue on LPNMR'19 papers
2021-08
The new Special Issue of Theory and Practice of Logic Programming on revised and extended papers presented at LPNMR'19 with Guest Editors Marcello Balduccini, Yuliya Lierler, and PI Stefan Woltran (also co-chair of LPNMR'19) is now available.
Binational PhD thesis on Treewidth-Based Problem Solving
2021-07
Team member Markus Hecher successfully defended his binational PhD thesis Advanced Tools and Methods for Treewidth-Based Problem Solving.
Congratulations!
Image (left to right): Markus Hecher, supervisor Stefan Woltran, and co-supervisor Torsten Schaub.
Erwin Schrödinger Research Funding
2021-05An Erwin Schrödinger research funding was granted to project member Jan Maly for his project "A holistic analysis of participatory budgeting". Soon the project will start and Jan will continue his work at the Institute of Logic, Language and Computation of the University of Amsterdam.
Invited talk at CILC 2020
2020-10PI Stefan Woltran was invited to give a talk at CILC 2020 titled "Computational Argumentation - Formal Models and Complexity Results".
The abstract can be found here.
Workshops and Competitions
2020-09Team member Markus Hecher co-organized the first international competition on model counting (MC 2020), the first international workshop on model counting (MCW 2020), and the 13th edition of the Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2020).
Moreover, PI Stefan Woltran and team members Martin Lackner and Jan Maly organized the First Vienna Workshop on Computational Social Choice.
All of the events were a great success!
PhD thesis on Ranking Sets of Objects
2020-09
Team member Jan Maly successfully defended his PhD thesis Ranking Sets of Objects: How to Deal with Impossibility Results.
The full thesis is available here.
Congratulations!
AAAI 2020: Two Accepted Papers
2020-02We are delighted to announce that two papers by team members have been accepted for presentation at this year's AAAI conference in New York.
PACE 2019 co-organization
2019-08
Team member Markus Hecher successfully co-organize this years PACE-Challenge. A report on the challenge can written by Johannes Fichte and Markus Hecher can be found in the FTP Newsletter.
Expansion-based QBF Solving on Tree Decompositions
2019-06Team member Günther Charwat published the paper "Expansion-based QBF Solving on Tree Decompositions" in Fundamenta Informaticae, vol. 167 describing the dynQBF system developed in the project.
LPNMR 2019 co-chair
2019-06
PI Stefan Woltran was co-chair for LPNMR 2019 (15th International Conference on Logic Programming and Nonmonotonic Reasoning). The conference took place in Philadelphia, USA on June 3 - 7, 2019.
Talk at Shonan Meeting 144
2019-03Team member Markus Hecher participated and gave a talk at the Shonan Meeting 144 "Parameterized Graph Algorithms & Data Reduction" in Shonan, Japan titled "Projected model counting using small treewidth". The slides can be found here.
AAAI 2019: Four Accepted Papers
2019-02We are delighted to announce that four papers by team members have been accepted for presentation at this year's AAAI conference in Hawaii. The conference proceedings are now available here.
Master thesis Andre Schidler
2019-01
Master student Andre Schidler presented his master thesis "A Solver for the Steiner Tree Problem with few Terminals" at the TU Epilog. The thesis was written under the supervision of PI Stefan Woltran and team member Johannes Fichte. The developed solver achieved the 4th place out of 12 participants in track A of the PACE 2018 competition.
taasp 2018
2018-11
TU Wien hosted this years edition of the taasp. workshop with invited talks by Vladimir Lifschitz, and Gerd Brewka. The workshop was co-organized by team members Michael Morak and Markus Hecher.
PACE 2019 co-organization
2018-11We are happy to announce that team member Markus Hecher will co-organize next years PACE-Challenge.
Stefan Woltran elected EurAI-Fellow
2018-08
Congratulations to PI Stefan Woltran, who has been elected a fellow of the European Association for Artificial Intelligence (EurAI).
KI Special Issue: Answer Set Programming Unleashed
2018-08
The new Special Issue of KI on Answer Set Programming by Guest Editors Torsten Schaub and Stefan Woltran is now available, answering the questions "What Answer Set Programming is about" and "What Answer Set Programming can do for you".
PACE'18 Challenge results
2018-09
Andre Schidler, Johannes Fichten and Markus Hecher successfully participated in the PACE'18 challenge and achieved the 4th place out of 12 participants in track A.
Thank you to the competition organizers!
For older news, see the news archive.
TopGoal of the Project
Handling computationally complex queries over huge data is an insurmountable obstacle for standard algorithms, thus novel methods are required. Our solution is to exploit structure. In reality, social networks are not random graphs and medical ontologies are not arbitrary sets of relations. Thus, structural parameters can serve as a key to apply recent techniques from the area of parameterized complexity. We shall focus here on the concept of decomposition (which divides the problem into smaller pieces making use of structural properties of the instance) and dynamic programming algorithms which solve the problem in terms of the decomposed instance. Notably, structure is not solely found in data like social networks but is also present in queries for complex reasoning (for instance, when seeking for a certain structure in molecules, this is naturally reflected in the query). The main vision of the decodyn project is to understand how structure can be simultaneously exploited on these two different levels, in such a way that (deco)mposition and (dyn)amic programming provide novel methods to make problems of this kind amenable to today's computers.
Several query languages which allow formalizations of complex reasoning tasks are nowadays available, among them variants of datalog or description logics. In the course of the project, we will first focus on Answer-Set Programming (also known as disjunctive datalog). In fact, Answer-Set Programming has shown great potential in the aforementioned application areas, but its use is still limited when problems of huge size have to be solved. In the second phase, we intend to migrate our results and methods to other reasoning paradigms and query languages.
TopProject Team
Current staff
Internal project partners
External project partners
Systems and Tools
Several systems delivered and extended in course of the project are publicly available.
Software
- D-FLAT family: D-FLAT is a flexible declarative framework allowing for rapid prototyping of dynamic programming algorithms over tree decompositions making use of ASP solvers. The tree decomposition is generated via heuristics and the developer only has to specify the dynamic programming algorithm in a declarative way as an ASP program.
- DynASP: DynASP is a dedicated ASP solver based on tree decomposition and dynamic programming. It is optimized for counting problems and supports the full ASP syntax.
- lpopt: lpopt is a tool to decompose logic programming rules, given in the syntax of ASP, into smaller, more manageable rules, that are easier to handle for current ASP solvers and grounders.
- htd: htd is a flexible and efficient software library that can be used to obtain tree decompositions of low width and other types of decompositions of a given input graph. It is used in D-FLAT, DynASP, dynBDD, dynQBF and dynClasp.
- dynQBF: dynQBF is a solver for quantified boolean formulae based on dynamic programming over tree decompositions. It can handle problem instances of high treewidth efficiently by relying on binary decision diagrams for the storage of the intermediate results.
Utilities and Playground
Here we collect further developed utilities, as well as prototypical software that is used to explore new ideas and concepts.- dynBDD: DynBDD works in a way that is similar to D-FLAT, but instead of storing the intermediate results explicitly, it uses binary decision diagrams in order to save memory and to increase performance and robustness in case of high treewidth.
- DecoVis: DecoVis is a visualization tool for the debugging and analysis of dynamic programming algorithms over tree decompositions. It provides a web front-end and benefits from powerful frameworks for graph visualization.
- dynClasp: dynClasp is an approach to exploit the heuristics of state-of-the-art answer set programming solvers in such a way that they follow the insights one can gain from tree decompositions with the goal to enhance performance.
- AdditionalStats and ClaspRe2: AdditionalStats and ClaspRe2 are tools to extract features (based on structural parameters from parameterized complexity theory) of ASP instances and classify them.
Publications
Here, we provide a comprehensive list of all project publications. Technical reports that document the project progress are listed subsequently.Technical Reports
Last updated: 2022-10-09 14:14