ERC Project: The Parameterized Complexity of Reasoning Problems

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
Robert Ganian, post-doc researcher
Ronald de Haan, pre-doc researcher
Eva Nedoma, administrative support
Friedrich Slivovsky, pre-doc researcher
Stefan Szeider, project leader
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)

de Haan, Fichte, Slivovsky, Gaspers, Ordyniak, Szeider, Bova, Ganian (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.

2015

A complete parameterized complexity analysis of bounded planning. Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider. Journal of Computer and System Sciences, volume 81, number 7, pages 1311-1332, 2015.
Model Counting for CNF Formulas of Bounded Modular Treewidth. Daniël Paulusma, Friedrich Slivovsky, Stefan Szeider. Algorithmica, July 2015.
A SAT Approach to Clique-Width. Marijn Heule, Stefan Szeider. ACM Trans. Comput. Log., volume 16, number 3, pages 24, 2015.
On finding optimal polytrees. Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, Stefan Szeider
Theoretical Computer Science, volume 592, pages 49-58, 2015.
Parameterized Complexity Results for Agenda Safety in Judgment Aggregation. Ulle Endriss, Ronald de Haan, and Stefan Szeider. Proceedings of AAMAS 2015, the 14th International Conference on Autonomous Agents and Multiagent Systems. Bordini, Elkind, Weiss, Yolum (eds.), May, 4-8, 2015, Istanbul, Turkey.
Complexity of the Winner Determination Problem in Judgment Aggregation: Kemeny, Slater, Tideman, Young. Ulle Endriss and Ronald de Haan. Proceedings of AAMAS 2015, the 14th International Conference on Autonomous Agents and Multiagent Systems. Bordini, Elkind, Weiss, Yolum (eds.), May, 4-8, 2015, Istanbul, Turkey.
On Compiling Structured CNFs to OBDDs. Simone Bova and Friedrich Slivovsky. In Proceedings of CSR 2015, 10th International Computer Science Symposium in Russia, 2015. pp. 80-93, Lecture Notes in Computer Science 9139, Springer, 2015.
[open access of author's self-archived copy at arxiv.org]
The Complexity of Equivalence, Entailment, and Minimization in Existential Positive Logic. Hubie Chen and Simone Bova. Journal of Computer and System Sciences, vol 81, no. 2, pp. 443-457, 2015.
On the Subexponential-Time Complexity of CSP. Ronald de Haan, Iyad A. Kanj, Stefan Szeider. Journal of Artificial Intelligence Research vol. 52, pp. 203-234, 2015.
[open access at publisher's website]
Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP. Ronald de Haan and Stefan Szeider. Proceedings of SOFSEM 2015, the 41st International Conference on Current Trends in Theory and Practice of Computer Science, Lecture Notes in Computer Science, vol. 8939, pp. 217-229, 2015.
[open access of author's self-archived copy at arxiv.org (Section 6)]
Backdoors to Tractable Answer-Set Programming. Johannes Klaus Fichte and Stefan Szeider. Artificial Intelligence vol. 220, pp. 64-103, 2015.
[open access of author's self-archived copy at arxiv.org]

2014

Quantified Conjunctive Queries on Partially Ordered Sets. Simone Bova, Robert Ganian, and Stefan Szeider. Proceedings of IPEC 2014, the 9th International Symposium on Parameterized and Exact Computation, September 10-12, 2014, Wroclaw, Poland. Lecture Notes in Computer Science vol. 8894, pp. 122-134, Springer, 2014.
[open access of author's self-archived copy at arxiv.org]
Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy. Ronald de Haan and Stefan Szeider. Electronic Colloquium on Computational Complexity, TR14-143, 2014
[open access at ECCC, TR14-143]
Small Unsatisfiable Subsets in Constraint Satisfaction. Ronald de Haan, Iyad Kanj, and Stefan Szeider. Proceedings of IEEE ICTAI 2014, the IEEE International Conference on Tools with Artificial Intelligence, Special Track on SAT and CSP Technologies, November 10-12, 2014, Limassol, Cyprus. IEEE, 2014.
[open access of author's self-archived copy at INFSYS repository, RR-1843-14-05]
Guarantees and Limits of Preprocessing in Constraint Satisfaction and Reasoning. Serge Gaspers and Stefan Szeider. Artificial Intelligence, vol. 216, pp. 1-19, 2014.
[open access of author's self-archived copy at arxiv.org]
Subexponential Time Complexity of CSP with Global Constraints. Ronald de Haan, Iyad Kanj, and Stefan Szeider. Proceedings of CP 2014, the 20th International Conference on Principles and Practice of Constraint Programming, Lyon, France, September 8-12, 2014, Lecture Notes in Computer Science no. 8656, pp. 272-288, Springer, 2014.
[open access of author's self-archived copy at INFSYS repository, RR-1843-14-06]
Fixed-Parameter Tractable Reductions to SAT. Ronald de Haan and Stefan Szeider. Proceedings of SAT 2014, the 17th International Conference on Theory and Applications of Satisfiability Testing, July 14-17, 2014, Vienna, Austria. Carsten Sinz and Uwe Egly (eds.), Lecture Notes in Computer Science, vol. 8561, pp. 85-102, Springer 2014.
[open access of author's self-archived copy at INFSYS repository, RR-1843-14-04]
Variable Dependencies and Q-Resolution. Friedrich Slivovsky and Stefan Szeider. Proceedings of SAT 2014, the 17th International Conference on Theory and Applications of Satisfiability Testing, July 14-17, 2014, Vienna, Austria. Carsten Sinz and Uwe Egly (eds.), Lecture Notes in Computer Science, vol. 8561, pp. 269-284, Springer 2014.
[open access of author's self-archived copy at INFSYS repository, RR-1843-14-09]
The Parameterized Complexity of Reasoning Problems Beyond NP. Ronald de Haan and Stefan Szeider. Proceedings of KR 2014, the 14th International Conference on Principles of Knowledge Representation and Reasoning, July 20-24, 2014, Vienna, Austria. Chitta Baral, Giuseppe De Giacomo, and Thomas Eiter (eds.), pp. 82-91, AAAI Press, 2014.
[open access of author's self-archived copy at arxiv.org]
Model Checking Existential Logic on Partially Ordered Sets. Simone Bova, Robert Ganian, and Stefan Szeider. Proceedings of CSL-LICS 2014, the Joint meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th ACM/IEEE Symposium on Logic in Computer Science (LICS), Vienna, Austria, July 14-18, 2014. Article no. 21, ACM, 2014.
[open access of author's self-archived copy at arxiv.org]
Backdoors into Heterogeneous Classes of SAT and CSP. Serge Gaspers, Neeldhara Misra, Sebastian Ordyniak, Stefan Szeider, and Stanislav Zivny. Proceedings of AAAI 2014, The Twenty-Eighth AAAI Conference on Artificial Intelligence, Quebec City, Quebec, Canada, July 27-31, 2014, Carla E. Brodley, Peter Stone (eds.), pp. 2652-2658, AAAI Press 2014.
[open access of author's self-archived copy at INFSYS repository, RR-1843-14-08]
The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation. Eun Jung Kim, Sebastian Ordyniak, and Stefan Szeider. Revised Selected papers of TAFA 2013, Theory and Applications of Formal Argumentation Second International Workshop, Beijing, China, August 3-5, 2013. Lecture Notes in Computer Science, vol. 8306, pp. 158-175, 2014.
[open access of author's self-archived copy at arxiv.org]
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, vol. 14, no. 2, March 2014, pp. 141-164.
[open access of author's self-archived copy at arxiv.org]
Unification and Projectivity in De Morgan and Kleene Algebras. Simone Bova and Leonardo Cabrer. Order, vol. 31, no. 2, July 2014, pp. 159-187.
[open access of author's self-archived copy at arxiv.org]
The Complexity of Width Minimization for Existential Positive Queries. Simone Bova and Hubie Chen. Proceedings of ICDT 2014, the 17th International Conference on Database Theory, Athens, March 24-28, 2014. OpenProceedings, pp. 235-244, 2014.
[open access via openproceedings.org]

Inside the ERC building in Brussels.

2013

Strong Backdoors to Bounded Treewidth SAT. Serge Gaspers and Stefan Szeider. Proceedings of FOCS 2013, The 54th Annual Symposium on Foundations of Computer Science, October 27-29, 2013, Berkeley, California, USA, pp. 489-498. Omer Reingold (ed.), IEEE, 2013.
[open access of author's self-archived copy at arxiv.org]
Model Counting for Formulas of Bounded Clique-Width. Friedrich Slivovsky and Stefan Szeider. Proceedings of ISAAC 2013, the 24th International Symposium on Algorithms and Computation, Hong Kong, December 16-18, 2013. Lecture Notes in Computer Science, vol. 8283, pp. 677-687, Springer 2013.
[open access of author's self-archived copy at arxiv.org]
Meta-kernelization with Structural Parameters. Robert Ganian, Friedrich Slivovsky, and Stefan Szeider. Proceedings of MFCS 2013, The 38th International Symposium on Mathematical Foundations of Computer Science, Klosterneuburg, Austria, August 26-30, 2013. Krishnendu Chatterjee and Jiri Sgall (eds.). Lecture Notes in Computer Science vol. 8087, pp. 457-468. Springer 2013.
[open access of author's self-archived copy at arxiv.org]
Revisiting Space in Proof Complexity: Treewidth and Pathwidth. Moritz Müller and Stefan Szeider. Proceedings of MFCS 2013, The 38th International Symposium on Mathematical Foundations of Computer Science, Klosterneuburg, Austria, August 26-30, 2013. Krishnendu Chatterjee and Jiri Sgall (eds.). Lecture Notes in Computer Science vol. 8087, pp. 704-716. Springer 2013.
[open access of author's self-archived copy at ECCC]
Backdoors to Abduction. Andreas Pfandler, Stefan Rümmele, and Stefan Szeider. Proceedings of IJCAI 2013, he 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013. Francesca Rossi (ed.). AAAI Press 2013.
[open access of author's self-archived copy at arxiv.org]
FO Model Checking of Interval Graphs. Robert Ganian, Petr Hliněný, Daniel Král, Jan Obdržálek, Jarett Schwartz, and Jakub Teska. Proceedings of ICALP 2013, The 40th International Colloquium on Automata, Languages and Programming, Riga, Latvia, July 8-12, 2013. Fedor V. Fomin and Rusins Freivalds and Marta Z. Kwiatkowska and David Peleg (eds.). Lecture Notes in Computer Science vol. 7966, pp. 250-262. Springer 2013.
[open access of author's self-archived copy at arxiv.org]
Parameterized Complexity Results for Plan Reuse. Ronald de Haan, Anna Roubickova, and Stefan Szeider. Proceedings of AAAI 2013, the 27th AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA. Marie des Jardins and Michael L. Littman (eds.), The AAAI Press, Palo Alto, California, pp. 224-231, 2013.
[open access of author's self-archived copy at arxiv.org]
Backdoors to Normality for Disjunctive Logic Programs. Johannes Klaus Fichte and Stefan Szeider. Proceedings of AAAI 2013, the 27th AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA. Marie des Jardins and Michael L. Littman (eds.), The AAAI Press, Palo Alto, California, pp. 320-327, 2013.
[open access of author's self-archived copy at arxiv.org]
On the Subexponential Time Complexity of CSP. Iyad Kanj and Stefan Szeider. Proceedings of AAAI 2013, the 27th AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA. Marie des Jardins and Michael L. Littman (eds.), The AAAI Press, Palo Alto, California, pp. 459-465, 2013.
[open access of author's self-archived copy at arxiv.org]
A SAT Approach to Clique-Width. Marijn Heule and Stefan Szeider. Proceedings of SAT 2013, The 16th International Conference on Theory and Applications of Satisfiability Testing, Helsinki, Finland, July 8-12, 2013. Matti Järvisalo and Allen Van Gelder (eds.), Lecture Notes in Computer Science vol. 7962, pp. 318-334, 2013.
[open access of author's self-archived copy at arxiv.org]
Local Backbones. Ronald de Haan, Iyad A. Kanj, and Stefan Szeider. Proceedings of SAT 2013, The 16th International Conference on Theory and Applications of Satisfiability Testing, Helsinki, Finland, July 8-12, 2013. Matti Järvisalo and Allen Van Gelder (eds.), Lecture Notes in Computer Science vol. 7962, pp. 377-393, 2013.
[open access of author's self-archived copy at arxiv.org]
Upper and Lower Bounds for Weak Backdoor Set Detection. Neeldhara Misra, Sebastian Ordyniak, Venkatesh Raman, and Stefan Szeider. Proceedings of SAT 2013, The 16th International Conference on Theory and Applications of Satisfiability Testing, Helsinki, Finland, July 8-12, 2013. Matti Järvisalo and Allen Van Gelder (eds.), Lecture Notes in Computer Science vol. 7962, pp. 394-402, 2013.
[open access of author's self-archived copy at arxiv.org]
Expanding the expressive power of Monadic Second-Order logic on restricted graph classes. Robert Ganian, Jan Obdržálek. Proceedings of IWOCA 2013, Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Rouen, France, July 10-12, 2013. Thierry Lecroq and Laurent Mouchard (eds.). Lecture Notes in Computer Science vol. 8288, pp. 164-177. Springer 2013.
[open access of author's self-archived copy at arxiv.org]
Unification and Projectivity in De Morgan and Kleene Algebras. Simone Bova and Leonardo Cabrer. Order, 10.1007/s11083-013-9295-3. June 2013.
[open access of author's self-archived copy at arxiv.org]
Parameterized Complexity and Kernel Bounds for Hard Planning Problems. Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, and Stefan Szeider. Proceedings of CIAC 2013, the 8th International Conference on Algorithms and Complexity, Barcelona, Spain, May 22-24, 2013. P. G. Spirakis and M. Serna, eds., Lecture Notes in Computer Science, vol. 7878, pp. 13-24, 2013.
[open access of author's self-archived copy at arxiv.org]
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

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 Symposium on Structure in Hard Combinatorial Problems, Structure 2013, at Vienna University of Technology, 16-18 May 2013, Vienna, Austria.
We have organised the third Workshop on Kernelization, WorKer 2011, at Vienna University of Technology, 2-4 September 2011, Vienna, Austria.
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.