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 > FAIR

Tools: Print

Project: FAIR - Fixed-Parameter Tractability in Artificial Intelligence and Reasoning

(funded by the Austrian Science Fund (FWF) under grant P25518)



Project started


The project has officially started on 2013-05-01 and will have a duration of three years.


Project team

Project leader

Project staff

Project partners


Goal of the Project

Reasoning is a fundamental task in Computer Science. It is concerned with the derivation of conclusions from some data or knowledge base. It has many interesting applications - especially in Artificial Intelligence - such as answer-set programming, reasoning on the web with description logics, belief revision, argumentation, diagnosis, etc. These areas have received vivid research interest in recent years. Strong theoretical foundations have been laid and algorithms have been presented which, at least in theory, solve the most common computational tasks in these areas. However, in practice, it has turned out that the high inherent complexity of most of these tasks is a severe obstacle to the application of these algorithms to problem instances of realistic size. To this date, the high computational complexity of reasoning tasks has not been satisfactorily solved.

Over the past decade, Parameterized Complexity Theory has evolved as a promising way of dealing with high complexity. The primary goal of a parameterized complexity analysis for some hard problem is to identify so-called fixed-parameter tractable fragments, i.e., to identify problem parameters that allow for the efficient solution of intractable problems in case these parameters are small. The tools of Parameterized Complexity Theory have been successfully applied to many areas of Computer Science - above all to hard problems in Graph Theory. However, the application of these techniques to hard reasoning problems is still in its infancy.

In this project, we want to extend the successful application of parameterized complexity techniques to the area of Artificial Intelligence and Reasoning. In the first place, we will thus initiate a systematic exploration of possible problem parameters and analyze their potential in finding tractable fragments of otherwise intractable reasoning problems. We will then harness the results of the Parameterized Complexity study to develop new efficient algorithms for fragments of hard reasoning problems and to identify directions for the improvement of existing solution methods for these problems.




  1. Martin Kronegger, Martin Lackner, Andreas Pfandler and Reinhard Pichler A Parameterized Complexity Analysis of Generalized CP-Nets In Proceedings of the 7th Multidisciplinary Workshop on Advances in Preference Handling (M-Pref'13), 2013.
    [ BibTeX ]
  2. Andreas Pfandler, Stefan Rümmele and Stefan Szeider Backdoors to Abduction In CoRR, abs/1304.5961, 2013.
    [ BibTeX ]
  3. Gábor Erdélyi, Martin Lackner and Andreas Pfandler Computational Aspects of Nearly Single-Peaked Electorates In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI-13), 2013.
    [ BibTeX ]
  4. Martin Kronegger, Andreas Pfandler and Reinhard Pichler Conformant Planning as a Benchmark for QBF-Solvers In Proc. of the International Workshop on Quantified Boolean Formulas (QBF 2013) colocated with SAT 2013, pages 1-5, 2013.
    [ BibTeX ]
  5. Petra Kaufmann, Martin Kronegger, Andreas Pfandler, Martina Seidl and Magdalena Widl Global State Checker: Towards SAT-Based Reachability Analysis of Communicating State Machines In Proc. of the 10th Model-Driven Engineering, Verification, and Validation Workshop (MoDeVVa 2013) colocated with MODELS 2013, pages 31-40, CEUR Workshop Proceedings , 2013.
    [ BibTeX ]
  6. Martin Lackner Incomplete Preferences in Single-Peaked Electorates In Proceedings of the 7th Multidisciplinary Workshop on Advances in Preference Handling (M-Pref'13), 2013.
    [ BibTeX ]
  7. Martin Kronegger, Andreas Pfandler and Reinhard Pichler Parameterized Complexity of Optimal Planning: A Detailed Map In Proc. of the 23rd International Joint Conference on Artificial Intelligence (IJCAI-13), AAAI Press, 2013.
    [ BibTeX ]
  8. Marie-Louise Bruner and Martin Lackner The computational landscape of permutation patterns In CoRR, abs/1301.0340, 2013, To appear in Pure and Applied Mathematics.
    [ BibTeX ]
Last updated: 2013-10-30 17:20

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist das Institut für Informationssysteme 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.