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 for which there is a strong theoretical evidence of intractability, but which may admit efficient solutions for special cases. 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. The ultimate goal is to understand the question: What makes a problem hard? Along these lines I have considered the boolean satisfiability problem (SAT), quantified boolean formulas (QBF), constraint satisfaction problems (CSP), and problems in graphs and networks.

Conference Activities

• 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 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.

Invited Talks

• 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 the Department of Computer Science, Royal Holloway, University of London, Computer Science Seminar, 24 February 2009.
• Invited speaker at Laboratoire d'Algorithmique et Image de Clermont-Ferrand, Seminar LAIC, Universite d'Auvergne, France, 13 November 2008.
• Invited speaker at Center for Discrete Mathematics and its Applications (DIMAP), DIMAP Seminar, University of Warwick, UK, 21 October 2008.
• 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.

Publications

Journal Papers | Conference Papers | Book Sections | Volumes Edited

Most of my papers are also listed at the DBLP Computer Science Bibliography. Try DBLP Viz for a visualization of coauthorship. My Erdös Number is 2.

Journal Papers

1. Solving MAX-r-SAT Above a Tight Lower Bound. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Algorithmica, to appear. Preliminary version appeared in SODA 2010.
2. 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, to appear.
3. The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT. Stefan Szeider. Discrete Optimization, to appear.
4. Monadic Second Order Logic on Graphs with Local Cardinality Constraints. Stefan Szeider. ACM Transactions on Computational Logic (TOCL), to appear.
5. Tractable Cases of the Extended Global Cardinality Constraint. Marko Samer and Stefan Szeider. Constraints, to appear.
6. Algorithms for Propositional Model Counting. Marko Samer and Stefan Szeider. J. of Discrete Algorithms, vol. 8, no. 1, pp. 50-64, 2010.
7. Constraint Satisfaction with Bounded Treewidth Revisited. Marko Samer and Stefan Szeider. Journal of Computer and System Sciences, vol. 76, no. 2, pp. 103-114, 2010.
8. 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. A preliminary and shortened version of this paper appeared in STOC'06.
9. 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.
10. Backdoor Sets of Quantified Boolean Formulas. Marko Samer and Stefan Szeider. Journal of Automated Reasoning, vol. 42, no. 1, pp. 77-97, 2009.
11. Fixed-Parameter Complexity of Minimum Profile Problems. Gregory Gutin, Stefan Szeider, and Anders Yeo. Algorithmica, vol. 52, no. 2, pp. 133-152, 2008.
12. Matched Formulas and Backdoor Sets. Stefan Szeider. Journal on Satisfiability, Boolean Modeling and Computation, vol. 6, pp. 1-12, 2008.
13. 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.
14. Solving #SAT Using Vertex Covers. Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. Acta Informatica, vol. 44, no. 7-8, pp. 509-523, 2007.
15. 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.
16. 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.
17. 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.
18. 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.
19. 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.
20. 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.
21. The Complexity of Resolution with Generalized Symmetry Rules. Stefan Szeider. Theory of Computing Systems, vol. 38, no. 2, pp. 171-188, 2005.
22. Generalizations of Matched CNF Formulas. Stefan Szeider. Annals of Mathematics and Artificial Intelligence, vol. 43, No. 1-4, pp. 223-238, 2005.
23. Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. Stefan Szeider. Journal of Computer and System Sciences, vol. 69, no. 4, pp. 656-674, 2004.
24. On Theorems Equivalent with Kotzig's Result on Graphs with Unique 1-Factors. Stefan Szeider. Ars Combinatoria, vol. 73, pp. 53-64, 2004.
25. Homomorphisms of Conjunctive Normal Forms. Stefan Szeider. Discrete Applied Mathematics, vol. 130 no. 2, pp. 351-365, 2003.
26. Finding Paths in Graphs Avoiding Forbidden Transitions. Stefan Szeider. Discrete Applied Mathematics, vol. 126, no. 2-3, pp. 239-251, 2003.
27. 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.

Conference Papers

Papers are listed only if there is not a corresponding journal paper (yet).

1. 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, to appear.
2. 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, to appear.
3. 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.
4. 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.
5. 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 Computer Science, Spindleruv Mlyn, Czech Republic. Lecture Notes in Computer Science 5901, p. 503-514, Springer, 2010.
6. Not So Easy Problems For Tree Decomposable Graphs. Stefan Szeider. Invited Talk. Proceedings of ICDM 2008, International Conference on Discrete Mathematics, June 6-10, 2008, Mysore, India, pp. 161-171.
7. 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.
8. 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.
9. 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.
10. Parameterized Proof Complexity. Stefan Dantchev, Barnaby Martin, and Stefan Szeider. FOCS 2007, The 48th Annual Symposium on Foundations of Computer Science, October 20-23, 2007, Providence, RI, USA, pp. 150-160, IEEE Press, 2007.
11. 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.
12. On the Complexity of Some Colorful Problems Parameterized by Treewidth. (invited paper) 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.
13. 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).
14. 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.
15. NP-Completeness of Refutability by Literal-Once Resolution. Stefan Szeider. Proceedings IJCAR 2001, Lecture Notes in Artificial Intelligence 2083, pp.168-181, 2001.

Book Sections

1. Parameterized SAT. Stefan Szeider. In Encyclopedia of Algorithms, edited by Ming-Yang Kao, Springer Verlag, 2008.
2. 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.

Volumes Edited

1. SAT 2010, Proceedings of the 13th International Conference on Theory and Applications of Satisfiability Testing. Ofer Strichman and Stefan Szeider (eds.). Lecture Notes in Computer Science, Volume 6175, Springer Verlag 2010.
2. Algorithms and Complexity in Durham 2007, Proceedings of the Third ACiD Workshop. Hajo Broersma, Stefan Dantchev, Matthew Johnson, and Stefan Szeider (eds.). Texts in Algorithmics 9, College Publications, London, 2007. We guest-edited a special issue of the Journal of Discrete Algorithms (Volume 8, Issue 2, June 2010) with selected papers from ACiD 2007.
3. Algorithms and Complexity in Durham 2006, Proceedings of the Second ACiD Workshop. Hajo Broersma, Stefan Dantchev, Matthew Johnson and Stefan Szeider (eds.). Texts in Algorithmics 7, College Publications, London, 2006. We guest-edited a special issue of the Journal of Discrete Algorithms (Volume 7, Issue 2, June 2009) with selected papers from ACiD 2006.
4. Algorithms and Complexity in Durham 2005, Proceedings of the First ACiD Workshop. Hajo Broersma, Stefan Dantchev, Matthew Johnson, and Stefan Szeider (eds.). Texts in Algorithmics 4, King's College Publications, London, 2005. We guest-edited a special issue of the Journal of Discrete Algorithms (Volume 6, Issue 4, 2008) with selected papers from ACiD 2005.