Stefan Szeider

Contact

Univ.-Prof. Dr. Stefan Szeider
Institute of Information Systems (184/3)
Vienna University of Technology (TU Wien)
Favoritenstraße 9-11
A-1040 Vienna, Austria

Phone: +43 (1) 58801 18433
Fax: +43 (1) 58801 18493
e-mail: stefan @ szeider.net

Research Interests

My work deals with the computational complexity of problems and their algorithmic solution. In particular I am interested in problems that are intractable in general but may admit efficient solutions for special cases. I have considered various problems arising in computational reasoning, artificial intelligence, and combinatorial optimization. My ambition is to push the intractability frontier for such problems as far as possible, aiming at an efficient solution for instances of practical relevance, and to identify the hard kernel of the general problem. My ultimate goal is to understand the question: What makes a problem hard?

Since 2009 I have been holding an ERC Starting Independent Researcher Grant for the research project "The Parameterized Complexity of Reasoning Problems".

Invited Talks

(Selection)

• Invited speaker at the workshop on Statistical Mechanics of Unsatisfiability and Glasses, Mariehamn, Finland, 23-26 May 2012.
• Invited speaker at APAC 2012 the first workshop on Applications of Parameterized Algorithms and Complexity, an affiliated workshop of ICALP 2012, Warwick, UK, July 8, 2012.
• Invited tutorial speaker at LI 2012, the Logic and Interactions Winter School at CIRM, Marseille, France, 30 January - 2 March, 2012.
• Invited plenary speaker at INAP 2011/WLP 2011, The 19th International Conference on Applications of Declarative Programming and Knowledge Management, and The 25th Workshop on Logic Programming, Vienna, Austria, 28-30 September 2011.
• Invited plenary speaker at JFPC/JIAF 2011, the 7th French Conference on Constraint Programming and the 5th French Conference on Artificial Intelligence, Lyon, France, 8-10 June, 2011.
• Invited speaker at ARW 2009, the Automated Reasoning Workshop 2009, Department of Computer Science, University of Liverpool, UK, 21-22 April 2009.
• Invited speaker at ICDM 2008, International Conference on Discrete Mathematics, Mysore, India, 6-10 June 2008.
• Invited speaker at SymCon'07, Seventh International Workshop on Symmetry and Constraint Satisfaction Problems, satellite workshop of CP 2007, Providence, RI, USA, 23 September 2007.

Conference Activities

• Member of the steering committee of IPEC, the International Symposium on Parameterized and Exact Computation (formerly IWPEC).
• Member of the steering committe of SAT, the International Conference on Theory and Applications of Satisfiability Testing.
• Conference co-chair of COMMA 2012, the Fourth International Conference on Computational Models of Argument, September 10-12, 2012, Vienna, Austria.
• Program commitee member of CP 2012, the 18th International Conference on Principles and Practice of Constraint Programming, 8-12th October 2012, Quebec City, Canada.
• Program commitee member of AAAI 2012, the 26th Conference on Artificial Intelligence, Toronto, Ontario, Canada, July 22-26, 2012.
• Program commitee member of SAT 2012, the Fifteen International Conference on Theory and Applications of Satisfiability Testing June 17-20, 2012, Trento, Italy.
• Chair of WorKer 2011, the Third Workshop on Kernelization, September 2-4, 2011, Vienna, Austria. .
• Program commitee member of SAT 2011, the Fourteenth International Conference on Theory and Applications of Satisfiability Testing June 19-22, 2011, Ann Arbor, USA.
• Program committee member of NECTAR 2011, Special Track on New Scientific and Technical Advances in Research; part of AAAI 2011, Twenty-Fifth AAAI Conference on Artificial Intelligence, San Francisco, USA, August 7-11, 2010.
• Chair of PCCR 2010, the first workshop on the Parameterized Complexity of Computational Reasoning, Satellite Workshop of the federated MFCS & CSL 2010 conference, Brno, Czech Republic, 28 August 2010.
• Co-chair of SAT 2010, Thirteenth International Conference on Theory and Applications of Satisfiability Testing, July 11-14, 2010, Edinburgh, UK, part of FLOC 2010, The Federated Logic Conference 2010.
• Program committee member of MFCS 2010, 35th International Symposium on Mathematical Foundations of Computer Science, Brno, Czech Republic, August 23-27, 2010.
• Program committee member of ISAIM 2010, 11th International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, Florida, January 6-8, 2010.
• Program committee member of NECTAR 2010, Special Track on New Scientific and Technical Advances in Research; part of AAAI 2010, Twenty-Fourth AAAI Conference on Artificial Intelligence, Atlanta, Georgia, USA, July 11-15, 2010.
• Program committee member of IWPEC 2009, 4th International Workshop on Parameterized and Exact Computation, 10-11 September 2009, IT University of Copenhagen, Denmark. Part of ALGO 2009.
• Program committee member of IJCAI 2009, Twenty-First International Joint Conference on Artificial Intelligence, July 11-17, 2009, Pasadena, California, USA.
• Program committee member of SAT 2009, Twelfth International Conference on Theory and Applications of Satisfiability Testing, 30 June - 3 July 2009, Swansea, Wales, United Kingdom.
• Program committee member of CATS 2009, Computing: The Australasian Theory Symposium, Wellington, New Zealand, January 20-23, 2009. Part of ASCW 2009, the Australasian Computer Science Week 2009.
• Program committee member of IWPEC 2008, Third International Workshop on Exact and Parameterized Computation, May 14-16, 2008, Victoria (BC), Canada. Colocated with STOC 2008.
• Program committee member of AAAI 2008, Twenty-Third AAAI Conference on Artificial Intelligence, Chicago, Illinois, USA, July 13-17, 2008.
• Program committee member of SAT 2008, Eleventh International Conference on Theory and Applications of Satisfiability Testing, May 12-15, 2008, Guangzhou, P. R. China.
• Co-organizer of ACiD 2007, Third Workshop on Algorithms and Complexity in Durham, September 17-19, 2007, University of Durham, England, UK.
• Program committee member of SAT 2007, Tenth International Conference on Theory and Applications of Satisfiability Testing, May 28-31, 2007, Lisbon, Portugal.
• Co-organizer of ACiD 2006, Second Workshop on Algorithms and Complexity in Durham, September 18-20, 2006, University of Durham, England, UK.
• Program committee member of SAT 2006, Ninth International Conference on Theory and Applications of Satisfiability Testing, August 12-15, 2006, Seattle, Washington, USA, affiliated to FLOC 2006.
• Program committee member of WADS 2005, The Workshop on Algorithms and Data Structures, August 15-17, 2005, University of Waterloo, Waterloo, Canada.
• Program committee member of SAT 2005, Eighth International Conference on Theory and Applications of Satisfiability Testing, June 19-23, 2005, University of St. Andrews, St. Andrews, Scotland, UK.
• Co-organizer of ACiD 2005, First Workshop on Algorithms and Complexity in Durham, July 8-10, 2005, University of Durham, England, UK.

Editorial Work

• Member of the editorial board of Fundamenta Informaticae.
• Guest co-editor of the J. of Discrete Algorithms, issues 6(4) 2008, 7(2) 2009, and 8(2) 2010.
• Co-editor of the Proceedings of SAT 2010, the 13th International Conference on Theory and Applications of Satisfiability Testing. Lecture Notes in Computer Science, Volume 6175, Springer Verlag 2010.
• Co-editor of the Proceedings of ACiD 2005, ACiD 2006, and ACiD 2007, the First, Second, and Third Workshop on Algorithms and Complexity in Durham, College Publications, London, 2005, 2006, and, 2007, respectively.

Publications

2012 or Forthcoming | 2011 | 2010 | 2009 | 2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2002 | 2001 | Technical Reports

Most of my papers are also listed at the DBLP Computer Science Bibliography. My Erdös Number is 2.

2012 or Forthcoming

1. 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, to appear.
2. 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. To appear.
3. 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. Springer-Verlag, 2012. To appear.
4. 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. Springer-Verlag, 2012. To appear.
5. 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. To appear.
6. 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. To appear.
7. 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. To appear.
8. 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.
9. Augmenting Tractable Fragments of Abstract Argumentation. Wolfgang Dvorak, Sebastian Ordyniak and Stefan Szeider. Artificial Intelligence, vol. 186, pp. 157-173, 2012.
10. On Contracting Graphs to Fixed Pattern Graphs. 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.
11. Editing Graphs to Satisfy Degree Constraints: A Parameterized Approach. Luke Mathieson and Stefan Szeider. J. of Computer and System Sciences, vol. 78, no. 1, pp. 179-191, 2012.
12. 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.

2011

1. Solving MAX-r-SAT Above a Tight Lower Bound. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Algorithmica, vol. 61, no. 3, 2011, pp. 638-655.
2. Parameterized Proof Complexity. Stefan Dantchev, Barnaby Martin, and Stefan Szeider. Computational Complexity, vol. 20, no. 1, pp. 51-85, 2011.
3. Algorithms and Complexity Results for Persuasive Argumentation. Eun Jung Kim, Sebastian Ordyniak, and Stefan Szeider. Artificial Intelligence, vol. 175, pp. 1722-1736, 2011.
4. Monadic Second Order Logic on Graphs with Local Cardinality Constraints. Stefan Szeider. ACM Transactions on Computational Logic, vol. 12, no. 2, article 12, 2011.
5. The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT. Stefan Szeider. Discrete Optimization, vol. 8, pp. 139-145, 2011.
6. A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds. Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. J. Computer and System Sciences, vol. 77, no. 2, pp. 422-429, 2011.
7. Tractable Cases of the Extended Global Cardinality Constraint. Marko Samer and Stefan Szeider. Constraints, vol. 16, no. 1, pp. 1-24, 2011.
8. On the Complexity of Some Colorful Problems Parameterized by Treewidth. M. Fellows, F. V. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider, C. Thomassen. Information and Computation, vol. 209, no. 2, pp. 143-153, 2011.
9. The Parameterized Complexity of Local Consistency. Serge Gaspers and Stefan Szeider. Proceedings of CP 2011, Principles and Practice of Constraint Programming, 17th International Conference, Perugia, Italy, September 12-16, 2011. pp 302-316, Lecture Notes in Computer Science vol. 6876, Springer, 2011.
10. Limits of Preprocessing. Stefan Szeider. Proceedings of the Twenty-Fifth Conference on Artificial Intelligence (AAAI 2011), pp. 93-98, AAAI Press, Menlo Park, California, 2011.
11. Kernels for Global Constraints. Serge Gaspers and Stefan Szeider. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2011), AAAI Press/IJCAI, pp. 540-545, 2011.
12. Augmenting Tractable Fragments of Abstract Argumentation. Sebastian Ordyniak and Stefan Szeider. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2011), AAAI Press/IJCAI, pp. 1033-1038, 2011. Full version to appear in Artificial Intelligence
13. Backdoors to Tractable Answer-Set Programming. Johannes Klaus Fichte and Stefan Szeider. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2011), AAAI Press/IJCAI, pp. 863-868, 2011.
14. 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.

2010

1. 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. Full version appeared in Algorithmica.
2. Algorithms for Propositional Model Counting. Marko Samer and Stefan Szeider. J. of Discrete Algorithms, vol. 8, no. 1, pp. 50-64, 2010.
3. Constraint Satisfaction with Bounded Treewidth Revisited. Marko Samer and Stefan Szeider. J. of Computer and System Sciences, vol. 76, no. 2, pp. 103-114, 2010.
4. Satisfiability of Acyclic and Almost Acyclic CNF Formulas. Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Proceedings of FSTTCS 2010, 30th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), pp. 84-95, 2010.
5. 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), December 13-15, 2010, IMSc, Chennai, India. Lecture Notes in Computer Science, vol. 6478, pp. 158-169, 2010. Full version to appear in Algorithmica.
6. 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.
7. 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. Full version appeared in Artificial Intelligence.
8. 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.
9. 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.
10. On Contracting Graphs to Fixed Pattern Graphs. Pim van't Hof, Marcin Kaminski, Daniel Paulusma, Stefan Szeider and Dimitrios M. Thilikos. Proceedings of SOFTSEM 2010, 36th International Conference on Current Trends in Theory and Practice of Computer Science, January 23-29, 2010, Spindleruv Mlyn, Czech Republic, Lecture Notes in Computer Science 5901, p. 503-514, Springer-Verlag 2010. Full version appeared in Discrete Applied Mathematics.
11. Not So Easy Problems For Tree Decomposable Graphs. Stefan Szeider. Invited Talk. Seclected 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

2009

1. Clique-Width is NP-Complete. Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. SIAM Journal on Discrete Mathematics vol. 23, no. 2, pp. 909-939, 2009.
2. Covering Graphs with Few Complete Bipartite Subgraphs. Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, and Stefan Szeider. Theoretical Computer Science, vol. 410, no. 21-23, pp. 2045-2053, 2009.
3. Backdoor Sets of Quantified Boolean Formulas. Marko Samer and Stefan Szeider. Journal of Automated Reasoning vol. 42, no. 1, pp. 77-97, 2009.
4. Matched Formulas and Backdoor Sets. Stefan Szeider. Journal on Satisfiability, Boolean Modeling and Computation, vol. 6, pp. 1-12, 2009.
5. A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds. Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Proceedings of IWPEC 2009, 4th International Workshop on Parameterized and Exact Computation, LNCS 5971, Springer, 2009. Full version appeared in the J. Computer and System Sciences.
6. The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT. Stefan Szeider. Proceedings of SAT 2009, Lecture Notes in Computer Science, vol. 5584, pp. 276-283, Springer, 2009. Full version appeared in Discrete Optimization.
7. Fixed-parameter Tractability. Marko Samer and Stefan Szeider. Chapter 13 of the Handbook of Satisfiability, edited by A. Biere, M. Heule, H. van Maaren, and T. Walsh. IOS Press, 2009.

2008

1. Fixed-Parameter Complexity of Minimum Profile Problems. Gregory Gutin, Stefan Szeider, and Anders Yeo. Algorithmica, vol. 52, no. 2, pp. 133-152, 2008.
2. Parameterized SAT. Stefan Szeider. In Encyclopedia of Algorithms, edited by Ming-Yang Kao, Springer Verlag, 2008.
3. Fixed-Parameter Algorithms for Artificial Intelligence, Constraint Satisfaction, and Database Problems. Georg Gottlob and Stefan Szeider. The Computer Journal, vol. 51, no. 3, pp. 303-325, 2008.
4. Backdoor Trees. Marko Samer and Stefan Szeider. Proceedings of AAAI 2008, Twenty-Third AAAI Conference on Artificial Intelligence, Chicago, Illinois, USA, July 13-17, 2008, pp. 363-368, AAAI Press, 2008.
5. Tractable Cases of the Extended Global Cardinality Constraint. Marko Samer and Stefan Szeider. Proceedings of CATS 2008, Computing: The Australasian Theory Symposium, University of Wollongong, New South Wales, Australia, January 22-25, 2008, part of the Australasian Computer Society Week (ACSW 2008), CRPIT vol. 77, pp. 67-74, Australian Computer Society, 2008. Full version appeared in Constraints.
6. Monadic Second Order Logic on Graphs with Local Cardinality Constraints. Stefan Szeider. Proceedings of MFCS 2008, 33rd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 5162, pp. 601-612, Springer-Verlag, 2008. Full version appeared in ACM Transactions on Computational Logic.
7. The Parameterized Complexity of Regular Subgraph Problems and Generalizations . Luke Mathieson and Stefan Szeider. Proceedings of CATS 2008, Computing: The Australasian Theory Symposium, University of Wollongong, New South Wales, Australia, January 22-25, 2008, part of the Australasian Computer Society Week (ACSW 2008), CRPIT vol. 77, pp. 79-86, Australian Computer Society, 2008. Full version appeared in the J. of Computer and System Sciences.
8. Parameterized Graph Editing with Chosen Vertex Degrees. Luke Mathieson and Stefan Szeider. Proceedings of COCOA 2008, 2nd Annual International Conference on Combinatorial Optimization and Applications, August 21-24, 2008, in St. John's, Newfoundland, Canada. Lecture Notes in Computer Science, vol. 5165, pp. 13-22, Springer-Verlag, 2008. Full version appeared in the J. of Computer and System Sciences.

2007

1. Parameterized Proof Complexity. Stefan Dantchev, Barnaby Martin, and Stefan Szeider. Proceedings of FOCS 2007, The 48th Annual Symposium on Foundations of Computer Science, October 20-23, 2007, Providence, RI, USA, pp. 150-160, IEEE Press, 2007. Full version appeared in Computational Complexity.
2. Solving #SAT Using Vertex Covers. Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. Acta Informatica, vol. 44, no. 7-8, pp. 509-523, 2007.
3. The Linear Arrangement Problem Parameterized Above Guaranteed Value. Gregory Gutin, Arash Rafiey, Stefan Szeider, and Anders Yeo. Theory of Computing Systems, vol. 41, pp. 521-538, 2007.
4. On the Complexity of Some Colorful Problems Parameterized by Treewidth. M. Fellows, F. V. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider, C. Thomassen. Proceedings of COCOA 2007, The First International Conference on Combinatorial Optimization and Applications, August 12-15, 2007, Xi'an, Shaanxi, China. Lecture Notes in Computer Science, vol. 4616, pp. 366-377, 2007. Full version appeared in Information and Computation.
5. Covering Graphs with Few Complete Bipartite Subgraphs. Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, and Stefan Szeider. Proceedings of FSTTCS 2007, the 27th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 4855, pp. 340-351, Springer-Verlag, 2007. Full version appeared in Theoretical Computer Science.
6. Without Loss of Generality -- Symmetric Reasoning for Resolution Systems. Stefan Szeider. Invited talk. Proceedings of SymCon'07, Seventh International Workshop on Symmetry and Constraint Satisfaction Problems, satellite workshop of CP 2007, September 23, 2007, Providence, RI, USA, pp. 5-8, 2007.
7. Backdoor Sets of Quantified Boolean Formulas. Marko Samer and Stefan Szeider. Proceedings of SAT 2007, Tenth International Conference on Theory and Applications of Satisfiability Testing, May 28-31, 2007, Lisbon, Portugal, Lecture Notes in Computer Science, vol. 4501, pp. 230-243, 2007. Full version appeared in Journal of Automated Reasoning.
8. Matched Formulas and Backdoor Sets. Stefan Szeider. Proceedings of SAT 2007, Lecture Notes in Computer Science, vol. 4501, pp. 94-99, 2007. Full version appeared in the Journal on Satisfiability, Boolean Modeling and Computation.

2006

1. Clique-Width Minimization is NP-hard. Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. A preliminary and shortened version of this paper appeared in the proceedings of STOC 2006; 38th ACM Symposium on Theory of Computing, Seattle, Washington, USA, pp. 354—362, ACM Press, 2006. Full version appeared in the SIAM Journal on Discrete Mathematics.
2. Covering Graphs with Few Complete Bipartite Subgraphs. Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, and Stefan Szeider. Theoretical Computer Science, vol. 410, no. 21-23, pp. 2045-2053, 2009.
3. A note on unsatisfiable k-CNF formulas with few occurrences per variable. Shlomo Hoory and Stefan Szeider. SIAM Journal on Discrete Mathematics, vol. 20, no. 2, pp. 523-528, 2006.
4. On Finding Short Resolution Refutations and Small Unsatisfiable Subsets. Michael R. Fellows, Stefan Szeider, and Graham Wrightson. Theoretical Computer Science, vol. 351, no. 3, pp. 351-359, 2006.
5. Constraint Satisfaction with Bounded Treewidth Revisited. Marko Samer and Stefan Szeider. Proceedings of CP 2006 , Twelfth International Conference on Principles and Practice of Constraint Programming, September 24-29, 2006, Nantes, France. Lecture Notes in Computer Science, vol. 4204, pp. 499—513, 2006. Full version appeared in the J. of Computer and System Sciences.
6. Fixed-Parameter Complexity of Minimum Profile Problems. Gregory Gutin, Stefan Szeider, and Anders Yeo. Proceedings of IWPEC 2006, 2nd International Workshop on Parameterized and Exact Computation, hosted by ALGO 2006, Zürich, Switzerland, September 13-15, 2006. Lecture Notes in Computer Science, vol. 4169, pp. 60-71, 2006. Full version appeared in Algorithmica.
7. Solving #SAT Using Vertex Covers. Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. Proceedings of SAT 2006, Ninth International Conference on Theory and Applications of Satisfiability Testing, August 12-15, 2006, Seattle, Washington, USA, Lecture Notes in Computer Science 4121, pp. 396—409, 2006. Full version appeared in Acta Informatica.

2005

1. On Edge-Colored Graphs Covered by Properly Colored Cycles. Herbert Fleischner and Stefan Szeider. Graphs and Combinatorics, vol. 21, no. 3, pp. 301-306, 2005.
2. Computing Unsatisfiable k-SAT Instances with Few Occurrences per Variable. Shlomo Hoory and Stefan Szeider. Theoretical Computer Science, vol. 337, no. 1-3, pp. 347-359, 2005.
3. Backdoor Sets for DLL Subsolvers. Stefan Szeider. Journal of Automated Reasoning, vol. 35, no. 1-3, pp.73-88, 2005. Reprinted as Chapter 4 of the book SAT 2005 - Satisfiability Research in the Year 2005, edited by E. Giunchiglia and T. Walsh, Springer Verlag, 2006.
4. The Complexity of Resolution with Generalized Symmetry Rules. Stefan Szeider. Theory of Computing Systems, vol. 38, no. 2, pp. 171-188, 2005.
5. Generalizations of Matched CNF Formulas. Stefan Szeider. Annals of Mathematics and Artificial Intelligence, vol. 43, No. 1-4, pp. 223-238, 2005.

2004

1. Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. Stefan Szeider. J. of Computer and System Sciences, vol. 69, no. 4, pp. 656-674, 2004.
2. On Theorems Equivalent with Kotzig's Result on Graphs with Unique 1-Factors. Stefan Szeider. Ars Combinatoria, vol. 73, pp. 53-64, 2004.
3. On Finding Short Resolution Refutations and Small Unsatisfiable Subsets. Michael R. Fellows, Stefan Szeider, and Graham Wrightson. Parameterized and Exact Computation, R. Downey, M. Fellows, F. Dehne, (eds.), Proceedings of the First International Workshop on Parameterized and Exact Computation (IWPEC04), Lecture Notes in Computer Science 3162, pp. 223-234, Springer Verlag, 2004. Full vesrion appeared in Theoretical Computer Science.
4. Computing Unsatisfiable k-SAT Instances with Few Occurrences per Variable. Shlomo Hoory and Stefan Szeider. SAT 2004. Full version appeared in Theoretical Computer Science.
5. Detecting Backdoor Sets with Respect to Horn and Binary Clauses. Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2004).

2003

1. Homomorphisms of Conjunctive Normal Forms. Stefan Szeider. Discrete Applied Mathematics, vol. 130 no. 2, pp. 351-365, 2003.
2. Finding Paths in Graphs Avoiding Forbidden Transitions. Stefan Szeider. Discrete Applied Mathematics, vol. 126, no. 2-3, pp. 239-251, 2003.
3. On Fixed-parameter Tractable Parameterizations of SAT. Stefan Szeider. Theory and Applications of Satisfiability (Selected and Revised Papers of SAT 2003) Lecture Notes in Computer Science 2919, pp. 188-202, 2004.
4. Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. Stefan Szeider. COCOON 2003. Full version appeared in the J. of Computer and System Sciences.
5. The Complexity of Resolution with Generalized Symmetry Rules. Stefan Szeider. Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science, STACS 2003, Eds.: H. Alt, M. Habib; Lecture Notes in Computer Science 2607, pp. 475-486, Springer Verlag 2003.) Full version appeared in Theory of Computing Systems.

2002

1. Polynomial-Time Recognition of Minimal Unsatisfiable Formulas with Fixed Clause-Variable Difference. Herbert Fleischner, Oliver Kullmann, and Stefan Szeider. Theoretical Computer Science, vol. 289, no. 1, pp. 503-516, 2002.

2001

1. NP-Completeness of Refutability by Literal-Once Resolution. Stefan Szeider. Proceedings IJCAR 2001, Lecture Notes in Artificial Intelligence 2083, pp.168-181, 2001.

Technical Reports

1. Strong Backdoors to Nested Satisfiabiliy. Serge Gaspers and Stefan Szeider. Technical Report, Arxiv.org: 1202.4331, February 2012.
2. Computing Resolution-Path Dependencies in Linear Time. Friedrich Slivovsky and Stefan Szeider. Technical Report, Arxiv.org: 1202.3097, February 2012.
3. Backdoors to Acyclic SAT. Serge Gaspers and Stefan Szeider. Technical Report, Arxiv.org: 1110.6384, October 2011.
4. Backdoors to Satisfaction. Serge Gaspers and Stefan Szeider. Survey paper. Arxiv.org: 1110.6387, October 2011.