Project Outline

Reasoning, to derive conclusions from facts, is a fundamental task in Artificial Intelligence that arises in a wide range of applications from Robotics to Expert Systems. Different applications require different forms of reasoning such as Nonmonotonic Reasoning (e.g., reasoning under the presence of default as- sumptions), Constraint-Based Reasoning (reasoning with forbidden configurations), and Bayesian Reasoning (reasoning with uncertain data). All these forms of reasoning give rise to computational problems that can be solved algorithmically. The efficiency of algorithms has a direct impact on applications; for example, improved algorithms for Bayesian inference yield more accurate computer assisted medical diagnosis.

The aim of this project is to devise new efficient algorithms for reasoning problems and to gain new theoretical insights into the question of what makes a reasoning problem hard, and what makes it easy. We study reasoning problems within the framework of Parameterized Complexity, a new and rapidly emerging field of Algorithms and Complexity. Parameterized Complexity takes structural aspects of problem instances into account which are most significant for empirically observed problem-hardness. Most of the considered reasoning problems are intractable in general, but the real-world context of their origin provides structural information that can be made accessible to algorithms in form of parameters. This makes Parameterized Complexity an ideal setting for the analysis and efficient solution of these problems that we want to explore.

Two inputs for a reasoning problem: random (left) and realistic (right).

An Illustration: the picture to the right shows the visualizations of two inputs for a reasoning problem. The input to the left is a random input. The input to the right is a real-world input (from multiplier verification). Both inputs have approximately the same size in bits, however, evidently the real-world instance is somehow "structured", whereas the random instance is not. The parameterized complexity approach allows to utilize this kind of structure to solve the problem efficiently.

Project Record

Project Title: The Parameterized Complexity of Reasoning Problems
Principle Investigator: Stefan Szeider
Funding Organization: European Research Council (ERC)
Project Type: ERC Starting Independent Researcher Grant
Project Volume: Eur 1.4 Mio
Project Duration: Jan 2010 - Dec 2014
Host Institution: Vienna University of Technology

Project Team

Simone Bova, post-doc researcher
Johannes Fichte, pre-doc researcher
Ronald de Haan, pre-doc researcher
Eva Nedoma, administrative support
Friedrich Slivovsky, pre-doc researcher
Stefan Szeider, project leader

Former Team Members

Yue Chen, pre-doc researcher (now: SFU, Canada)
Serge Gaspers, post-doc researcher (now: University of NSW and NICTA, Australia)
Sebastian Ordyniak, post-doc researcher (now: Masaryk University, Czech Republic)

The project team, May 2012. Ordyniak, Nedoma, Gaspers, Fichte, Chen, Slivovsky, Szeider (from left to right).

Publications

Project publications are available under open access as required by the ERC. For each publication we provide a link to a free copy, either to the publisher's web site, or to a repository with a self-archived copy of the paper. We provide this link immediately or within a few months after publication.

Inside the ERC building in Brussels.

2013

  • Satisfiability of Acyclic and Almost Acyclic CNF Formulas Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Theoretical Computer Science, vol. 481, pp. 85-99, 2013.
    [open access of author's self-archived copy at arxiv.org]
  • Parameterized Complexity Results for Exact Bayesian Network Structure Learning. Sebastian Ordyniak and Stefan Szeider. Journal of Artificial Intelligence Research, vol. 46, pp. 263-302, 2013.
    [open access at publisher's website]
  • Model Counting for CNF Formulas of Bounded Modular Treewidth. Daniel Paulusma, Friedrich Slivovsky, and Stefan Szeider. Proceedings of STACS 2013, The 30th Symposium on Theoretical Aspects of Computer Science, Kiel, Germany, February 27-March 2, 2013. Natacha Portier and Thomas Wilke (eds.), Leibniz International Proceedings in Informatics, vol. 20, pp 55-66, 2013.
    [open access at publisher's website]
  • Backdoors to q-Horn. Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, and Stefan Szeider. Proceedings of STACS 2013, The 30th Symposium on Theoretical Aspects of Computer Science, Kiel, Germany, February 27-March 2, 2013. Natacha Portier and Thomas Wilke (eds.), Leibniz International Proceedings in Informatics, vol. 20, pp 67-79, 2013.
    [open access at publisher's website]

2012

  • Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough. Reinhard Pichler, Stefan Rümmele, Stefan Szeider and Stefan Woltran. Theory and Practice of Logic Programming, FirstView Article, July 2012, pp. 1-24.
    [open access of author's self-archived copy at arxiv.org]
  • Backdoors to Acyclic SAT. Serge Gaspers and Stefan Szeider. Proceedings of ICALP 2012 (Track A: Algorithms, Complexity and Games), the 39th International Colloquium on Automata, Languages and Programming, 9-13 July 2012, University of Warwick, UK. Lecture Notes in Computer Science, vol. 7391, pp. 363-374, Springer-Verlag, 2012.
    [open access of author's self-archived copy at arxiv.org]
  • Abstract Argumentation via Monadic Second Order Logic. Wolfgang Dvorak, Stefan Szeider, and Stefan Woltran. Proceedings of SUM 2012, Sixth International Conference on Scalable Uncertainty Management, Marburg, Germany, September 17-19, 2012. Lecture Notes in Computer Science, vol. 7520, pp. 85-98, Springer 2012.
    [open access of author's self-archived copy at DBAI repository, TR-2012-79]
  • The Complexity of Planning Revisited — A Parameterized Analysis. Christer Bäckström, Yue Chen, Peter Jonsson, Sebastian Ordyniak, and Stefan Szeider. Proceedings of AAAI 2012, the 26th Conference on Artificial Intelligence, Toronto, Ontario, Canada, July 22-26, 2012. pp. 1735-1741, AAAI Press, 2012.
    [open access of author's self-archived copy at arxiv.org]
  • On Finding Optimal Polytrees. Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, and Stefan Szeider. Proceedings of AAAI 2012, the 26th Conference on Artificial Intelligence, Toronto, Ontario, Canada, July 22-26, 2012. pp. 750-756, AAAI Press, 2012.
    [open access of author's self-archived copy at arxiv.org]
  • Don't Be Strict in Local Search! Serge Gaspers, Eun Jung Kim, Sebastian Ordyniak, Saket Saurabh, and Stefan Szeider. Proceedings of AAAI 2012, the 26th Conference on Artificial Intelligence, Toronto, Ontario, Canada, July 22-26, 2012. pp. 486-492, AAAI Press, 2012.
    [open access of author's self-archived copy at arxiv.org]
  • Computing Resolution-Path Dependencies in Linear Time. Friedrich Slivovsky and Stefan Szeider. Proceedings of SAT 2012, the Fifteen International Conference on Theory and Applications of Satisfiability Testing June 17-20, 2012, Trento, Italy. Lecture Notes in Computer Science, vol. 7317, pp. 58-71, Springer-Verlag, 2012.
    [open access of author's self-archived copy at arxiv.org]
  • Strong Backdoors to Nested Satisfiability. Serge Gaspers and Stefan Szeider. Proceedings of SAT 2012, the Fifteen International Conference on Theory and Applications of Satisfiability Testing June 17-20, 2012, Trento, Italy. Lecture Notes in Computer Science, vol. 7317, pp. 72-85, Springer-Verlag, 2012.
    [open access of author's self-archived copy at arxiv.org]
  • Backdoors to Satisfaction. Serge Gaspers and Stefan Szeider. Survey paper. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Complexity Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, vol. 370, pp. 287-317, Springer Verlag, 2012.
    [open access of author's self-archived copy at arxiv.org]
  • The Good, the Bad, and the Odd: Cycles in Answer-Set Programs. Johannes Klaus Fichte. New Directions in Logic, Language and Computation. Selected, revised, and expanded papers from the ESSLLI 2010 and the ESLLI 2011 Student Sessions. Lecture Notes in Computer Science, vol. 7415, pp. 78-90, Springer 2012.
    [open access of author's self-archived copy at arxiv.org]
  • Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming. Gregory Gutin, Eun Jung Kim, Arezou Soleimanfallah, Stefan Szeider and Anders Yeo. Algorithmica vol. 64, no. 1, pp. 112-125, 2012.
    [open access of author's self-archived copy at arxiv.org]
  • Augmenting Tractable Fragments of Abstract Argumentation. Wolfgang Dvorak, Sebastian Ordyniak and Stefan Szeider. Artificial Intelligence, vol. 186, pp. 157-173, 2012.
    [open access via the AIJ Editorial Website]
  • On Graph Contractions and Induced Minors. Pim van't Hof, Marcin Kaminski, Daniel Paulusma, Stefan Szeider and Dimitrios M. Thilikos. Discrete Applied Mathematics, vol. 160, no. 6, pp. 799-809, 2012.
    [open access of author's self-archived copy at INFSYS repository, RR-1843-12-06]
  • k-Gap Interval Graphs. Fedor V. Fomin, Serge Gaspers, Petr Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, and Yngve Villanger. Proceedings of LATIN 2012, The 10th Latin American Theoretical Informatics Symposium, April 16-20, 2012, Arequipa, Peru. Lecture Notes in Computer Science, vol. 7256, pp. 350-361, Springer, 2012.
    [open access of author's self-archived copy at arxiv.org]
  • Editing Graphs to Satisfy Degree Constraints: A Parameterized Approach. Luke Mathieson and Stefan Szeider. Journal of Computer and System Sciences, vol. 78, no. 1, pp. 179-191, 2012.
    [open access of author's self-archived copy at INFSYS repository, RR-1843-12-01]

2011

  • A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds. Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Journal of Computer and System Sciences, vol. 77, no. 2, pp. 422-429, 2011.
    [open access of author's self-archived copy at INFSYS repository, RR-1843-11-04]
  • Monadic Second Order Logic on Graphs with Local Cardinality Constraints. Stefan Szeider. ACM Transactions on Computational Logic, vol. 12, no. 2, article 12, 2011.
    [open access at publisher's web site]
  • The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT. Stefan Szeider. Discrete Optimization, vol. 8, pp. 139-145, 2011.
    [open access of author's self-archived copy at INFSYS repository, RR-1843-11-05]
  • Algorithms and Complexity Results for Persuasive Argumentation. Eun Jung Kim, Sebastian Ordyniak, and Stefan Szeider. Artificial Intelligence, vol. 175, pp. 1722-1736, 2011.
    [open access via the AIJ Editorial Website]
  • Satisfiability of Acyclic and Almost Acyclic CNF Formulas (II). Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Proceedings of SAT 2011, Fourteenth International Conference on Theory and Applications of Satisfiability Testing June 19-22, 2011, Ann Arbor, USA. Lecture Notes in Computer Science vol. 6695, pp. 47-60, Springer, 2011.
    [open access of author's self-archived copy at arxiv.org]
  • Kernels for Global Constraints. Serge Gaspers and Stefan Szeider. Proceedings of IJCAI 2011, the International Joint Conference on Artificial Intelligence, AAAI Press/IJCAI, pp. 540-545, 2011.
    [open access at publisher's web site]
  • Augmenting Tractable Fragments of Abstract Argumentation. Sebastian Ordyniak and Stefan Szeider. Proceedings of IJCAI 2011, the International Joint Conference on Artificial Intelligence, AAAI Press/IJCAI, pp. 1033-1038, 2011.
    [open access at publisher's web site]
  • Backdoors to Tractable Answer-Set Programming. Johannes Klaus Fichte and Stefan Szeider. Proceedings of IJCAI 2011, the International Joint Conference on Artificial Intelligence, AAAI Press/IJCAI, pp. 863-868, 2011.
    [open access at publisher's web site]
  • Limits of Preprocessing. Stefan Szeider. Proceedings of AAAI 2011, the Twenty-Fifth Conference on Artificial Intelligence, pp. 93-98, AAAI Press, Menlo Park, California, 2011.
    [open access at publisher's web site]
  • The Parameterized Complexity of Local Consistency. Serge Gaspers and Stefan Szeider. Proceedings of CP 2011, Principles and Practice of Constraint Programming, 17th International Conference, pp 302-316, Lecture Notes in Computer Science vol. 6876, Springer, 2011.
    [open access of author's self-archived copy at ECCC]
  • Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. Albert Atserias, Johannes Klaus Fichte, Marc Thurley. Journal of Artificial Intelligence Research, vol. 40, no. 1, pp. 353-373, 2011
    [open access at publisher's website]
  • The Good, the Bad, and the Odd: Cycles in Answer-Set Programs. Johannes Klaus Fichte. Proc. of the ESSLLI 2011 Student Session (23rd European Summer School in Logic, Language, and Information), pp. 78-86, 2011.
    [open access at organizer's website]
  • Complexity of Splits Reconstruction for Low-Degree Trees. Serge Gaspers, Mathieu Liedloff, Maya J. Stein, and Karol Suchan. Proceedings of WG 2011, the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science vol. 6986, pp. 167-178, Springer 2011.
    [open access of author's self-archived copy at arxiv.org]
  • Towards Finding Optimal Polytrees. Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, Stefan Szeider. NIPS Workshop on Discrete Optimization in Machine Learning (DISCML 2011): Uncertainty, Generalization and Feedback. Sierra Nevada, Spain, 17 December 2011.
    [open access at workshop website]
  • An Improved Dynamic Progamming Algorithm for Exact Bayesian Network Structure Learning. Sebastian Ordyniak and Stefan Szeider. NIPS Workshop on Discrete Optimization in Machine Learning (DISCML 2011): Uncertainty, Generalization and Feedback. Sierra Nevada, Spain, 17 December 2011.
    [open access at workshop website]

2010

  • Solving MAX-r-SAT Above a Tight Lower Bound. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Proceedings of SODA 2010, the Twenty-First ACM-SIAM Symposium on Discrete Algorithms, pp. 511-517, SIAM, 2010.
    [open access at publisher's web site]
  • Satisfiability of Acyclic and Almost Acyclic CNF Formulas. Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Proceedings of FSTTCS 2010, the 30th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), pp. 84-95, 2010.
    [open access at publisher's web site]
  • Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming. Gregory Gutin, Eun Jung Kim, Arezou Soleimanfallah, Stefan Szeider and Anders Yeo. Proceedings of IPEC 2010, International Symposium on Parameterized and Exact Computation (formerly IWPEC). Lecture Notes in Computer Science, vol. 6478, pp. 158-169, 2010.
    [open access of author's self-archived copy at INFSYS repository, RR-1843-11-02]
  • Parameterizing by the Number of Numbers. Michael R. Fellows, Serge Gaspers, Frances A. Rosamond. Proceedings of IPEC 2010, International Symposium on Parameterized and Exact Computation (formerly IWPEC). Lecture Notes in Computer Science, vol. 6478, pp. 123-134, 2010.
    [open access of author's self-archived copy at arxiv.org]
  • Algorithms and Complexity Results for Persuasive Argumentation. Eun Jung Kim, Sebastian Ordyniak and Stefan Szeider. Proceedings of COMMA 2010, Third International Conference on Computational Models of Argument, Desenzano del Garda, Italy, September 8-10, 2010. Froniers in Artificial Intelligence and Applications, vol. 216, IOS Press, 2010, pp. 311-322.
    [open access of author's self-archived copy at INFSYS repository, RR-1843-11-03]
  • Reasoning in Argumentation Frameworks of Bounded Clique-Width. Wolfgang Dvovrak, Stefan Szeider, and Stefan Woltran. Proceedings of COMMA 2010, Third International Conference on Computational Models of Argument, Desenzano del Garda, Italy, September 8-10, 2010. Froniers in Artificial Intelligence and Applications, vol. 216, IOS Press, 2010, pp. 219-230.
    [open access of author's self-archived copy at DBAI repository, TR-2011-71]
  • Algorithms and Complexity Results for Exact Bayesian Structure Learning. Sebastian Ordyniak and Stefan Szeider. Proceedings of UAI 2010, The 26th Conference on Uncertainty in Artificial Intelligence, Catalina Island, California, USA, July 8-11, 2010. Peter Grünwald and Peter Spirtes (eds.), AUAI Press, Corvallis, pp. 401-408, 2010.
    [open access at conference web site]
  • Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough. Reinhard Pichler, Stefan Rümmele, Stefan Szeider and Stefan Woltran. Proceedings of KR 2010, Twelfth International Conference on Principles of Knowledge Representation and Reasoning Toronto, Canada, May 9-13, 2010, AAAI Press 2010.
    [open access at publisher's web site]
  • Not So Easy Problems For Tree Decomposable Graphs. Stefan Szeider. Selected and revised papers of ICDM 2008, International Conference on Discrete Mathematics, June 6-10, 2008, Mysore, India. RMS Lecture Notes Series no. 13, pp. 179-190. Ramanujan Mathematical Society, 2010
    [open access of author's self-archived copy at arxiv.org]

Events

  • We have organised the first workshop on Parameterized Complexity of Computational Reasoning, PCCR 2010, as a Satellite Workshop of MFCS & CSL 2010, Brno, Czech Republic, 28 August 2010.
  • We have organised the third Workshop on Kernelization, WorKer 2011, at Vienna University of Technology, 2-4 September 2011, Vienna, Austria.