Publications: Stefan Szeider
2026
OBDDs, SDDs, and Circuits of Bounded Width: Completeness Matters
Alexis De Colnet and Sebastian Ordyniak and Stefan Szeider
Artificial Intelligence, volume 351, pages 104458, 2026.
[pdf] [doi] [details]
Backdoors to Satisfaction Continued
Serge Gaspers and Stefan Szeider
Computer Science Review, volume 60, pages 100868, 2026.
[pdf] [doi] [details]
Graph Choosability via SAT: Beyond the Nullstellensatz
Markus Kirchweger, Tomás Peitl, David Seka, Stefan Szeider
The 40th Annual AAAI Conference on Artificial Intelligence, AAAI-2026, 2026.
Note: To appear
[details]
A General Theoretical Framework for Learning Smallest Interpretable Models
Sebastian Ordyniak and Giacomo Paesani and Mateusz Rychlicki and Stefan Szeider
Artificial Intelligence, volume 350, pages 104441, 2026.
[pdf] [doi] [details]
Computing Probabilistic Explanations for ML Models: Fixed-Parameter Algorithms
Ordyniak, Sebastian, Rychlicki, Mateusz, Szeider, Stefan
The 40th Annual AAAI Conference on Artificial Intelligence, AAAI-2026, 2026.
Note: To appear
[details]
2025
Uncovering and Verifying Optimal Community Structure in Complex Networks: A MaxSAT Approach
Carlos Ansótegui and Vaidyanathan Peruvemba Ramaswamy and Stefan Szeider and Hai Xia
Computational Science - ICCS 2025 - 25th International Conference, Singapore, July 7-9, 2025, Proceedings, Part II (Michael H. Lees and Wentong Cai and Siew Ann Cheong and Yi Su and David Abramson and Jack J. Dongarra and Peter M. A. Sloot), volume 15904 of Lecture Notes in Computer Science, pages 35-49, 2025, Springer.
[pdf] [doi] [details]
Analyzing Reformulation Performance in Core-Guided MaxSAT Solving
André Schidler and Stefan Szeider
28th International Conference on Theory and Applications of Satisfiability Testing, SAT 2025, August 12-15, 2025, Glasgow, Scotland (Jeremias Berg and Jakob Nordström), volume 341 of LIPIcs, pages 26:1-26:18, 2025, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]
Extracting Problem Structure with LLMs for Optimized SAT Local Search
André Schidler, Stefan Szeider
SOCS 2025, The 18th International Symposium on Combinatorial Search. August 12-15, 2025. University of Glasgow, Scotland, United Kingdom, 2025.
[pdf] [details]
Large and Parallel Human Sorting Networks
Szeider, Stefan
Creative Mathematical Sciences Communication (Fernau, Henning and Schwank, Inge and Staub, Jacqueline), pages 194-204, 2025, Springer Nature Switzerland.
[doi] [details]
Bridging Language Models and Symbolic Solvers via the Model Context Protocol
Stefan Szeider
28th International Conference on Theory and Applications of Satisfiability Testing, SAT 2025, August 12-15, 2025, Glasgow, Scotland (Jeremias Berg and Jakob Nordström), volume 341 of LIPIcs, pages 30:1-30:12, 2025, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]
SAT Modulo Symmetries: A Survey
Stefan Szeider
Satisfiability Checking and Symbolic Computation, 10th International Workshop, SC-Square 2025, Stuttgart, Germany, August 2, 2025, co-located with CADE 2025, volume 4116 of CEUR Workshop Proceedings, pages 1-11, 2025, CEUR-WS.org.
[pdf] [details]
StreamLLM: Enhancing Constraint Programming with Large Language Model-Generated Streamliners
Voboril, Florentina, Peruvemba Ramaswamy, Vaidyanathan, Szeider, Stefan
2025 IEEE/ACM 1st International Workshop on Neuro-Symbolic Software Engineering (NSE), pages 17-22, 5 2025, IEEE.
[pdf] [doi] [details]
Generating Streamlining Constraints with Large Language Models
Florentina Voboril, Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider
Journal of Artificial Intelligence Research, volume 84, pages 16:1-16:19, 2025.
[details]
The 3-Decomposition Conjecture: A SAT-Based Approach with Specialized Propagators
Tianwei Zhang and Stefan Szeider
31st International Conference on Principles and Practice of Constraint Programming, CP 2025, August 10-15, 2025, Glasgow, Scotland (Maria Garcia de la Banda), volume 340 of LIPIcs, pages 39:1-39:19, 2025, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]
2024
Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
Leroy Chew, Alexis de Colnet, Friedrich Slivovsky, Stefan Szeider
AAAI'24, the Thirty-Eighth AAAI Conference on Artificial Intelligence, February 20-27, Vancouver, Canada (Jennifer Dy and Sriraam Natarajan), pages 7978-7986, 2024, AAAI Press.
[pdf] [doi] [details]
ASP-QRAT: A Conditionally Optimal Dual Proof System for ASP
Chew, Leroy, de Colnet, Alexis, Szeider, Stefan
Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, pages 253-263, 8 2024.
[pdf] [doi] [details]
Learning Small Decision Trees for Data of Low Rank-Width
Konrad Dabrowski, Eduard Eiben, Sebastian Ordyniak, Giacomo Paesani, Stefan Szeider
AAAI'24, the Thirty-Eighth AAAI Conference on Artificial Intelligence, February 20-27, Vancouver, Canada (Jennifer Dy and Sriraam Natarajan), pages 10476-10483, 2024, AAAI Press.
[pdf] [doi] [details]
Compilation and Fast Model Counting beyond CNF
Alexis de Colnet, Stefan Szeider, Tianwei Zhang
Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24 (Kate Larson), pages 3315-3323, 8 2024, International Joint Conferences on Artificial Intelligence Organization.
Note: Main Track
[doi] [details]
SAT backdoors: Depth beats size
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
Journal of Computer and System Sciences, volume 142, pages 103520, 2024.
[doi] [details]
Revisiting Causal Discovery from a Complexity-Theoretic Perspective
Robert Ganian, Viktoriia Korchemna, Stefan Szeider
Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24 (Kate Larson), pages 3377-3385, 8 2024, International Joint Conferences on Artificial Intelligence Organization.
Note: Main Track
[doi] [details]
SAT Modulo Symmetries for Graph Generation and Enumeration
Markus Kirchweger, Stefan Szeider
ACM Transactions on Computational Logic, volume 25, number 3, 2024.
[doi] [details]
Computing small Rainbow Cycle Numbers with SAT modulo Symmetries
Markus Kirchweger, Stefan Szeider
The 30th International Conference on Principles and Practice of Constraint Programming, CP 2024 (Paul Shaw), 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[details]
A General Theoretical Framework for Learning Smallest Interpretable Models
Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki, Stefan Szeider
AAAI'24, the Thirty-Eighth AAAI Conference on Artificial Intelligence, February 20-27, Vancouver, Canada (Jennifer Dy and Sriraam Natarajan), pages 10662-10669, 2024, AAAI Press.
[pdf] [doi] [details]
Explaining Decisions in ML Models: A Parameterized Complexity Analysis
Ordyniak, Sebastian, Paesani, Giacomo and Rychlicki, Mateusz, Szeider, Stefan
Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, pages 563-573, 8 2024.
[pdf] [doi] [details]
Backdoor DNFs
Sebastian Ordyniak, Andre Schidler, Stefan Szeider
Journal of Computer and System Sciences, volume 144, pages 103547, 2024.
[doi] [details]
The Power of Collaboration: Learning Large Bayesian Networks at Scale
Ramaswamy, Vaidyanathan Peruvemba, Szeider, Stefan, Xia, Hai
2024 IEEE 36th International Conference on Tools with Artificial Intelligence (ICTAI), pages 371-378, 2024.
[doi] [details]
eSLIM: Circuit Minimization with SAT Based Local Improvement
Franz-Xaver Reichl, Friedrich Slivovsky and Stefan Szeider
27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024) (Chakraborty, Supratik and Jiang, Jie-Hong Roland), volume 305 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1-23:14, 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[doi] [details]
Improved Circuit Minimization with Exact Synthesis
Franz-Xaver Reichl, Friedrich Slivovsky, Stefan Szeider
2024, Technical report AC-TR-24-001, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
SAT-based Decision Tree Learning for Large Data Sets
André Schidler, Stefan Szeider
Journal of Artificial Intelligence Research, volume 80, pages 875-918, 2024.
[details]
Structure-guided Local Improvement for Maximum Satisfiability
André Schidler, Stefan Szeider
The 30th International Conference on Principles and Practice of Constraint Programming, CP 2024 (Paul Shaw), 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[details]
SAT-Based Tree Decomposition with Iterative Cascading Policy Selection
Hai Xia, Stefan Szeider
AAAI'24, the Thirty-Eighth AAAI Conference on Artificial Intelligence, February 20-27, Vancouver, Canada (Jennifer Dy and Sriraam Natarajan), pages 8191-8199, 2024, AAAI Press.
[pdf] [doi] [details]
Small unsatisfiable k-CNFs with bounded literal occurrence
Tianwei Zhang , Tomáš Peitl, Stefan Szeider
27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024) (Chakraborty, Supratik and Jiang, Jie-Hong Roland), volume 305 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:22, 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[doi] [details]
2023
Learning Small Decision Trees with Large Domain
Eduard Eiben, Sebastian Ordyniak, Giacomo Paesani, Stefan Szeider
The 32nd International Joint Conference on Artificial Intelligence (IJCAI-23), August 19–25, 2023, Macao, S.A.R. (Edith Elkind), pages 3184-3192, 2023, International Joint Conferences on Artificial Intelligence Organization.
Note: Main Track
[pdf] [doi] [details]
IPASIR-UP: User Propagators for CDCL
Katalin Fazekas, Aina Niemetz, Mathias Preiner and Markus Kirchweger, Stefan Szeider, Armin Biere
The 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023), July 04-08, 2023, Alghero, Italy (Meena Mahajan and Friedrich Slivovsky), volume 271 of LIPIcs, pages 8:1-8:13, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[doi] [details]
Inconsistent Cores for ASP: The Perks and Perils of Non-Monotonicity
Johannes K. Fichte, Markus Hecher, Stefan Szeider
Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023 (Brian Williams and Yiling Chen and Jennifer Neville), pages 6363-6371, 2023, AAAI Press.
[pdf] [doi] [details]
The Silent (R)evolution of SAT
Johannes K. Fichte, Daniel Le Berre, Markus Hecher, Stefan Szeider
Communications of the ACM, volume 66, number 6, pages 64-72, June 2023.
[doi] [details]
Co-Certificate Learning with SAT Modulo Symmetries
Markus Kirchweger, Tomáš Peitl, Stefan Szeider
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 1944-1953, 2023, ijcai.org.
Note: Main Track
[pdf] [doi] [details]
SAT-Based Generation of Planar Graphs
Markus Kirchweger, Manfred Scheucher, Stefan Szeider
The 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023), July 04-08, 2023, Alghero, Italy (Meena Mahajan and Friedrich Slivovsky), volume 271 of LIPIcs, pages 14:1-14:18, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[doi] [details]
The Parameterized Complexity of Finding Concise Local Explanations
Sebastian Ordyniak, Giacomo Paesani, Stefan Szeider
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 3312-3320, 2023, ijcai.org.
[pdf] [doi] [details]
Are Hitting Formulas Hard for Resolution?
Tomáš Peitl and Stefan Szeider
Discr. Appl. Math., volume 337, pages 173-184, 2023.
[doi] [details]
Circuit Minimization with QBF-Based Exact Synthesis
Franz-Xaver Reichl, Friedrich Slivovsky, Stefan Szeider
Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023 (Brian Williams and Yiling Chen and Jennifer Neville), pages 4087-4094, 2023, AAAI Press.
[pdf] [doi] [details]
Circuit Minimization with Exact Synthesis: From QBF Back to SAT
Franz-Xaver Reichl and Friedrich Slivovsky and Stefan Szeider
Proceedings of the 32nd International Workshop on Logic & Synthesis (IWLS), 2023.
[details]
Computing twin-width with SAT and branch & bound
Andre Schidler, Stefan Szeider
The 32nd International Joint Conference on Artificial Intelligence (IJCAI-23), August 19–25, 2023, Macao, S.A.R. (Edith Elkind), pages 2013-2021, 2023, International Joint Conferences on Artificial Intelligence Organization.
Note: Main Track
[pdf] [doi] [details]
SAT-Boosted Tabu Search for Coloring Massive Graphs
Andre Schidler, Stefan Szeider
J. Exp. Algorithmics, volume 2825, number 1.5, pages 1-19, 2023.
[doi] [details]
Computing optimal hypertree decompositions with SAT
André Schidler and Stefan Szeider
Artificial Intelligence, volume 325, pages 104015, 2023.
[pdf] [doi] [details]
Proven optimally-balanced Latin rectangles with SAT
Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider
Proceedings of CP 2023, the 29th International Conference on Principles and Practice of Constraint Programming (Roland Yap), volume 280 of LIPIcs, pages 48:1-48:10, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]
Searching for smallest universal graphs and tournaments with SAT
Tianwei Zhang, Stefan Szeider
Proceedings of CP 2023, the 29th International Conference on Principles and Practice of Constraint Programming (Roland Yap), volume 280 of LIPIcs, pages 39:1-39:20, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]
2022
CSP Beyond Tractable Constraint Languages
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
28th International Conference on Principles and Practice of Constraint Programming, CP 2022, July 31 to August 8, 2022, Haifa, Israel (Christine Solnon), volume 235 of LIPIcs, pages 20:1-20:17, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]
Tractable Abstract Argumentation via Backdoor-Treewidth
Wolfgang Dvorak, Markus Hecher, Matthias König and Andre Schidler, Stefan Szeider, Stefan Woltran
Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, pages 5608-5615, 2022, AAAI Press.
[pdf] [details]
Finding a Cluster in Incomplete Data
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider
30th Annual European Symposium on Algorithms (ESA 2022) (Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1-47:14, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]
Sum-of-Products with Default Values: Algorithms and Complexity Results
Robert Ganian, Eun Jung Kim, Friedrich Slivovsky, Stefan Szeider
Journal of Artificial Intelligence Research, volume 33, pages 535-552, 2022.
[pdf] [details]
Algorithmic Applications of Tree-Cut Width
Robert Ganian, Eun Jung Kim, Stefan Szeider
SIAM J. Discrete Math., volume 36, number 4, pages 2635-2666, 2022.
[pdf] [doi] [details]
Threshold Treewidth and Hypertree Width
Robert Ganian, Andre Schidler, Manuel Sorge, Stefan Szeider
Journal of Artificial Intelligence Research, volume 74, pages 1687-1713, 2022.
[pdf] [doi] [details]
Weighted Model Counting with Twin-Width
Robert Ganian, Filip Pokr ́yvka, Andre Schidler, Kirill Simonov, Stefan Szeider
25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022, August 2-5, 2022, Haifa, Israel (Kuldeep S. Meel and Ofer Strichman), volume 236 of LIPIcs, pages 15:1-15:17, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]
A SAT Attack on Rota’s Basis Conjecture
Markus Kirchweger, Manferd Scheucher, Stefan Szeider
25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022, August 2-5, 2022, Haifa, Israel (Kuldeep S. Meel and Ofer Strichman), volume 236 of LIPIcs, pages 4:1-4:18, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]
A SAT Approach to Twin-Width
André Schidler, Stefan Szeider
Proceedings of ALENEX 2022, the 24nd SIAM Symposium on Algorithm Engineering and Experiments (Cynthia A. Phillips and Bettina Speckmann), pages 67-77, 2022, SIAM.
[doi] [details]
Learning Large Bayesian Networks with Expert Constraints
Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider
38th Conference on Uncertainty in Artificial Intelligence (UAI 2022), Eindhoven, Netherlands, August 1–5, 2022 (James Cussens and Kun Zhang), pages 180:1592–1601, 2022.
[details]
2021
The Parameterized Complexity of Clustering Incomplete Data
Eduard Eiben, Robert Ganian, Iyad Kanj and Sebastian Ordyniak, Stefan Szeider
Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 7296-7304, 2021, AAAI Press.
[pdf] [details]
The Parameterized Complexity of Clustering Incomplete Data
Eduard Eiben, Robert Ganian, Iyad Kanj and Sebastian Ordyniak, Stefan Szeider
2021, Technical report AC-TR-21-007, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
New Width Parameters for SAT and Sharp-SAT
Ganian, Robert, Szeider, Stefan
Artificial Intelligence, volume 295, pages 103460, 2021.
[pdf] [doi] [details]
SAT Modulo Symmetries for Graph Generation
Markus Kirchweger, Stefan Szeider
Proceeings of CP 2021, the 27th International Conference on Principles and Practice of Constraint Programming (Laurent D. Michel), pages 39:1–-39:17, 2021, Dagstuhl Publishing.
[doi] [details]
Backdoor DNFs
Sebastian Ordyniak, Andre Schidler, Stefan Szeider
Proceeding of IJCAI-2021, the 30th International Joint Conference on Artificial Intelligence (Zhi-Hua Zhou), pages 1403-1409, 2021.
[doi] [details]
Backdoor DNFs
Sebastian Ordyniak, André Schidler, Stefan Szeider
2021, Technical report AC-TR-21-001, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Parameterized Complexity of Small Decision Tree Learning
Sebastian Ordyniak, Stefan Szeider
Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 6454-6462, 2021, AAAI Press.
[pdf] [details]
Parameterized Complexity of Small Decision Tree Learning
Sebastian Ordyniak, André Schidler, Stefan Szeider
2021, Technical report AC-TR-21-002, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Finding the Hardest Formulas for Resolution (Extended Abstract)
Tomáš Peitl and Stefan Szeider
Proceeding of IJCAI-21, the 30th International Joint Conference on Artificial Intelligence (Zhi-Hua Zhou), pages 4814-4818, 2021.
Note: Sister Conferences Best Papers
[doi] [details]
Finding the Hardest Formulas for Resolution
Tomáš Peitl, Stefan Szeider
Journal of Artificial Intelligence Research, volume 72, pages 69-97, 2021.
Note: Conference Award Track, best paper CP 2020
[doi] [details]
Certified DQBF Solving by Definition Extraction
Franz-Xaver Reichl, Friedrich Slivovsky, Stefan Szeider
2021, Technical report AC-TR-21-010, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Certified DQBF Solving by Definition Extraction
Franz-Xaver Reichl and Friedrich Slivovsky and Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2021 - 24th International Conference, Barcelona, Spain, July 5-9, 2021, Proceedings (Chu-Min Li and Felip Manyà), volume 12831 of Lecture Notes in Computer Science, pages 499-517, 2021, Springer.
[pdf] [doi] [details]
Fixed-Parameter Tractability
Marko Samer, Stefan Szeider
Chapter in Handbook of Satisfiability, 2nd Edition (Armin Biere and Marijn Heule and Hans van Maaren and Toby Walsh), pages 693-736, 2021, IOS Press.
[pdf] [doi] [details]
Fixed-Parameter Tractability
Marko Samer, Stefan Szeider
2021, Technical report AC-TR-21-004, Algorithms and Complexity Group, TU Wien.
Note: Chapter 17, Handbook of Satisfiability, 2nd Edition, 2021
[pdf] [details]
SAT-based Decision Tree Learning for Large Data Sets
André Schidler, Stefan Szeider
Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 3904-3912, 2021, AAAI Press.
[pdf] [details]
Computing Optimal Hypertree Decompositions with SAT
Andre Schidler, Stefan Szeider
Proceeding of IJCAI-21, the 30th International Joint Conference on Artificial Intelligence (Zhi-Hua Zhou), 2021.
[doi] [details]
SAT-based Decision Tree Learning for Large Data Sets
André Schidler, Stefan Szeider
2021, Technical report AC-TR-21-003, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Turbocharging Treewidth-Bounded Bayesian Network Structure Learning
Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider
Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 3895-3903, 2021, AAAI Press.
[pdf] [details]
Learning fast-inference Bayesian networks
Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider
Proceedings of NeurIPS 2021, the Thirty-fifth Conference on Neural Information Processing Systems (M. Ranzato and A. Beygelzimer and K. Nguyen and P.S. Liang and J.W. Vaughan and Y. Dauphin), pages 17852-17863, 2021.
[pdf] [details]
2020
A Time Leap Challenge for SAT-Solving
Johannes K. Fichte, Markus Hecher, Stefan Szeider
Proceedings of CP 2020, the 26th International Conference on Principles and Practice of Constraint Programming (Helmut Simonis), volume 12333 of Lecture Notes in Computer Science, pages 267-285, 2020, Springer Verlag.
[details]
Breaking Symmetries with RootClique and LexTopsort
Johannes K. Fichte, Markus Hecher, Stefan Szeider
Proceedings of CP 2020, the 26th International Conference on Principles and Practice of Constraint Programming (Helmut Simonis), volume 12333 of Lecture Notes in Computer Science, pages 286-303, 2020, Springer Verlag.
[details]
Breaking Symmetries with RootClique and LexTopsort
Johannes K. Fichte, Markus Hecher, Stefan Szeider
2020, Technical report AC-TR-20-010, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Rank
Robert Ganian, Iyad Kanj, Sebastian Ordyniak and Stefan Szeider
Proceeding of AAAI-20, the Thirty-Fourth AAAI Conference on Artificial Intelligence, February 7–12, 2020, New York, pages 3906-3913, 2020, AAAI Press.
[pdf] [details]
On the Parameterized Complexity of Clustering
Robert Ganian, Iyad Kanj, Sebastian Ordyniak and Stefan Szeider
2020, Technical report AC-TR-20-002, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Fixed-Parameter Tractability of Dependency QBF with Structural Parameters
Robert Ganian, Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
2020, Technical report AC-TR-20-011, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Threshold Treewidth and Hypertree Width
Robert Ganian, Andre Schidler, Manuel Sorge, Stefan Szeider
Proceeding of IJCAI-PRICAI2020, the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence, pages 1898-1904, 2020.
[pdf] [doi] [details]
Formalizing Graph Trail Properties in Isabelle/HOL
Laura Kovács and Hanna Lachnitt and Stefan Szeider
Intelligent Computer Mathematics - 13th International Conference, CICM 2020, Bertinoro, Italy, July 26-31, 2020, Proceedings (Christoph Benzmüller and Bruce R. Miller), volume 12236 of Lecture Notes in Computer Science, pages 190-205, 2020, Springer Verlag.
[details]
Formalizing Graph Trail Properties in Isabelle/HOL
Laura Kovács and Hanna Lachnitt and Stefan Szeider
2020, Technical report AC-TR-20-012, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Finding the Hardest Formulas for Resolution
Tomáš Peitl, Stefan Szeider
Proceedings of CP 2020, the 26th International Conference on Principles and Practice of Constraint Programming (Helmut Simonis), volume 12333 of Lecture Notes in Computer Science, pages 514-530, 2020, Springer Verlag.
Note: Best Paper Award
[details]
Finding the Hardest Formulas for Resolution
Tomáš Peitl, Stefan Szeider
2020, Technical report AC-TR-20-008, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Computing Optimal Hypertree Decompositions
André Schidler, Stefan Szeider
Proceedings of ALENEX 2020, the 22nd SIAM Symposium on Algorithm Engineering and Experiments (Guy Blelloch and Irene Finocchi), pages 1-11, 2020, SIAM.
[details]
Computing Optimal Hypertree Decompositions
André Schidler, Stefan Szeider
2020, Technical report AC-TR-20-001, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Short Q-Resolution Proofs with Homomorphisms
Ankit Shukla, Friedrich Slivovsky, Stefan Szeider
Proceedings of SAT 2020, The 23rd International Conference on Theory and Applications of Satisfiability Testing (Luca Pulina and Martina Seidl), volume 12178 of Lecture Notes in Computer Science, pages 412-428, 2020, Springer Verlag.
[details]
Short Q-Resolution Proofs with Homomorphisms
Ankit Shukla, Friedrich Slivovsky, Stefan Szeider
2020, Technical report AC-TR-20-007, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth
Friedrich Slivovsky, Stefan Szeider
Proceedings of SAT 2020, The 23rd International Conference on Theory and Applications of Satisfiability Testing (Luca Pulina and Martina Seidl), volume 12178 of Lecture Notes in Computer Science, pages 267-276, 2020, Springer Verlag.
[details]
A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth
Friedrich Slivovsky, Stefan Szeider
2020, Technical report AC-TR-20-006, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
MaxSAT-Based Postprocessing for Treedepth
Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider
Proceedings of CP 2020, the 26th International Conference on Principles and Practice of Constraint Programming (Helmut Simonis), volume 12333 of Lecture Notes in Computer Science, pages 478-495, 2020, Springer Verlag.
[doi] [details]
MaxSAT-Based Postprocessing for Treedepth
Vaidyanathan P. R., Stefan Szeider
2020, Technical report AC-TR-20-009, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
2019
Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
de Haan, Ronald and Stefan Szeider
MDPI Algorithms, volume 12, number 9, pages 1-28, 2019.
[doi] [details]
The Parameterized Complexity of Cascading Portfolio Scheduling
Eduard Eiben, Robert Ganian, Iyad Kanj and Stefan Szeider
Proceedings of NeurIPS 2019, the Thirty-third Conference on Neural Information Processing Systems (Hanna M. Wallach and Hugo Larochelle and Alina Beygelzimer and Florence d’Alché-Buc and Emily B. Fox and Roman Garnett), pages 7666-7676, 2019.
[pdf] [details]
The Parameterized Complexity of Cascading Portfolio Scheduling
Eduard Eiben, Robert Ganian, Iyad Kanj and Stefan Szeider
2019, Technical report AC-TR-19-009, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
SAT-Encodings for Treecut Width and Treedepth
Robert Ganian, Neha Lodha, Sebastian Ordyniak and Stefan Szeider
Proceedings of ALENEX 2019, the 21st Workshop on Algorithm Engineering and Experiments (Stephen G. Kobourov and Henning Meyerhenke), pages 117-129, 2019, SIAM.
[pdf] [doi] [details]
SAT-Encodings for Treecut Width and Treedepth
Robert Ganian, Neha Lodha, Sebastian Ordyniak and Stefan Szeider
2019, Technical report AC-TR-19-001, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
A Join-Based Hybrid Parameter for Constraint Satisfaction
Robert Ganian, Sebastian Ordyniak, Stefan Szeider
Proceedings of CP 2019, the 25th International Conference on Principles and Practice of Constraint Programming (Thomas Schiex and Simon de Givry), volume 11802 of Lecture Notes in Computer Science, pages 195-212, 2019, Springer Verlag.
[pdf] [doi] [details]
A Join-Based Hybrid Parameter for Constraint Satisfaction
Robert Ganian, Sebastian Ordyniak, Stefan Szeider
2019, Technical report AC-TR-19-006, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
A SAT Approach to Branchwidth
Neha Lodha and Sebastian Ordyniak and Stefan Szeider
ACM Transactions on Computational Logic, volume 20, number 3, pages 15:1-15:24, 2019.
[pdf] [doi] [details]
A SAT Approach to Branchwidth
Neha Lodha and Sebastian Ordyniak and Stefan Szeider
2019, Technical report AC-TR-19-010, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
On the Parameterized Complexity of (k,s)-SAT
Daniël~Paulusma, Stefan Szeider
Information Processing Letters, volume 143, pages 34-36, 2019.
[doi] [details]
Long-Distance Q-Resolution with Dependency Schemes
Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
Journal of Automated Reasoning, volume 63, number 1, pages 127-155, 2019.
[pdf] [doi] [details]
Dependency Learning for QBF
Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
Journal of Artificial Intelligence Research, volume 65, pages 180-208, 2019.
[pdf] [doi] [details]
Combining Resolution-Path Dependencies with Dependency Learning
Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
Proceedings of SAT 2019, the 22nd International Conference on Theory and Applications of Satisfiability Testing, July 7–12, 2019, Lisbon, Portugal (Mikoláš Janota and Inês Lynce), volume 11628 of Lecture Notes in Computer Science, pages 306-318, 2019, Springer Verlag.
[doi] [details]
Proof Complexity of Fragments of Long-Distance Q-resolution
Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
Proceedings of SAT 2019, the 22nd International Conference on Theory and Applications of Satisfiability Testing, July 7–12, 2019, Lisbon, Portugal (Mikoláš Janota and Inês Lynce), volume 11628 of Lecture Notes in Computer Science, pages 319-335, 2019, Springer Verlag.
[doi] [details]
Proof Complexity of Fragments of Long-Distance Q-resolution
Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
2019, Technical report AC-TR-19-004, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Combining Resolution-Path Dependencies with Dependency Learning
Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
2019, Technical report AC-TR-19-005, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
2018
Solving Problems on Graphs of High Rank-Width
Eduard Eiben, Robert Ganian, Stefan Szeider
Algorithmica, volume 80, number 2, pages 742-771, 2018.
[pdf] [doi] [details]
An SMT Approach to Fractional Hypertree Width
Johannes K. Fichte, Markus Hecher, Neha Lodha and Stefan Szeider
Proceedings of CP 2018, the 24rd International Conference on Principles and Practice of Constraint Programming (John N. Hooker), volume 11008 of Lecture Notes in Computer Science, pages 109-127, 2018, Springer Verlag.
[doi] [details]
An SMT Approach to Fractional Hypertree Width
Johannes K. Fichte, Markus Hecher, Neha Lodha and Stefan Szeider
2018, Technical report AC-TR-18-006, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Parameterized Algorithms for the Matrix Completion Problem
Robert Ganian, Iyad Kanj, Sebastian Ordyniak and Stefan Szeider
Proceeding of ICML, the Thirty-fifth International Conference on Machine Learning, Stockholm, July 10–15, 2018, pages 1642-1651, 2018, JMLR.org.
Note: ISSN: 1938-7228
[pdf] [details]
Sum-of-Products with Default Values: Algorithms and Complexity Results
Robert Ganian, Eun Jung Kim, Friedrich Slivovsky, Stefan Szeider
Proceedings of ICTAI 2018, the 30th IEEE International Conference on Tools with Artificial Intelligence (Lefteri H. Tsoukalas and Éric Grégoire and Miltiadis Alamaniotis), pages 733-737, 2018, IEEE.
[pdf] [doi] [details]
Sum-of-Products with Default Values: Algorithms and Complexity Results
Robert Ganian, Eun Jung Kim, Friedrich Slivovsky and Stefan Szeider
2018, Technical report AC-TR-18-007, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Portfolio-Based Algorithm Selection for Circuit QBFs
Holger H. Hoos, Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
Proceedings of CP 2018, the 24rd International Conference on Principles and Practice of Constraint Programming (John N. Hooker), volume 11008 of Lecture Notes in Computer Science, pages 195-209, 2018, Springer Verlag.
[doi] [details]
Portfolio-Based Algorithm Selection for Circuit QBFs
Hoos, Holger H., Peitl, Tomáš, Slivovsky, Friedrich, Szeider, Stefan
QBF Workshop, 2018.
[details]
Portfolio Solvers for QDIMACS and QCIR
Hoos, Holger H., Peitl, Tomáš and Slivovsky, Friedrich, Szeider, Stefan
2018.
Note: QBF Evaluation at SAT
[details]
Portfolio-Based Algorithm Selection for Circuit QBFs
Holger H. Hoos, Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
2018, Technical report AC-TR-18-004, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
On the Parameterized Complexity of (k,s)-SAT
Daniël~Paulusma, Stefan Szeider
2018, Technical report AC-TR-18-008, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Polynomial-Time Validation of QCDCL Certificates
Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
Proceedings of SAT 2018, the 21st International Conference on Theory and Applications of Satisfiability Testing, Part of FLoC 2018, July 9–12, 2018, Oxford, UK (Olaf Beyersdorff and Christoph M. Wintersteiger), volume 10929 of Lecture Notes in Computer Science, pages 253-269, 2018, Springer Verlag.
[pdf] [doi] [details]
Polynomial-Time Validation of QCDCL Certificates
Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
2018, Technical report AC-TR-18-003, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
2017
Circuit Treewidth, Sentential Decision, and Query Compilation
Simone Bova, Stefan Szeider
Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017 (Emanuel Sallinger and Jan Van den Bussche and Floris Geerts), pages 233-246, 2017, ACM.
[pdf] [doi] [details]
On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances
Ronald de Haan, Iyad Kanj, Stefan Szeider
2017, Technical report AC-TR-17-009, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Parameterized Complexity Classes Beyond Para-NP
Ronald de Haan, Stefan Szeider
Journal of Computer and System Sciences, volume 87, number AC-TR-17-004, pages 16-57, 2017.
[pdf] [doi] [details]
SAT-Based Local Improvement for Finding Tree Decompositions of Small Width
Johannes K. Fichte, Neha Lodha, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings (Serge Gaspers and Toby Walsh), volume 10491 of Lecture Notes in Computer Science, pages 401-411, 2017, Springer Verlag.
[doi] [details]
SAT-Based Local Improvement for Finding Tree Decompositions of Small Width
Johannes K. Fichte, Neha Lodha, Stefan Szeider
2017, Technical report AC-TR-17-015, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Backdoor Trees for Answer Set Programming
Johannes Klaus Fichte and Stefan Szeider
Proceedings of the 10th Workshop on Answer Set Programming and Other Computing Paradigms co-located with the 14th International Conference on Logic Programming and Nonmonotonic Reasoning, ASPOCP@LPNMR 2017, Espoo, Finland, July 3, 2017. (Bart Bogaerts and Amelia Harrison), volume 1868 of CEUR Workshop Proceedings, 2017, CEUR-WS.org.
[pdf] [details]
Backdoor Treewidth for SAT
Robert Ganian, M. S. Ramanujan, Stefan Szeider
2017, Technical report AC-TR-17-014, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Combining Treewidth and Backdoors for CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) (Heribert Vollmer and Vall ́ee), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1-36:17, 2017, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[pdf] [doi] [details]
Backdoor Treewidth for SAT
Robert Ganian, M. S. Ramanujan, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings (Serge Gaspers and Toby Walsh), volume 10491 of Lecture Notes in Computer Science, pages 20-37, 2017, Springer Verlag.
[pdf] [doi] [details]
New Width Parameters for Model Counting
Robert Ganian, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings (Serge Gaspers and Toby Walsh), volume 10491 of Lecture Notes in Computer Science, pages 38-52, 2017, Springer Verlag.
[pdf] [doi] [details]
New Width Parameters for Model Counting
Robert Ganian, Stefan Szeider
2017, Technical report AC-TR-17-013, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Backdoors into heterogeneous classes of SAT and CSP
Serge Gaspers and Neeldhara Misra and Sebastian Ordyniak and Stefan Szeider and Stanislav Zivny
Journal of Computer and System Sciences, volume 85, pages 38-56, 2017.
[pdf] [doi] [details]
Backdoor Sets for CSP
Serge Gaspers and Sebastian Ordyniak and Stefan Szeider
Chapter in The Constraint Satisfaction Problem: Complexity and Approximability (Andrei A. Krokhin and Stanislav Zivny), volume 7 of Dagstuhl Follow-Ups, pages 137-157, 2017, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[pdf] [doi] [details]
On the parameterized complexity of finding small unsatisfiable subsets of CNF formulas and CSP instances
de Haan, Ronald, Kanj, Iyad, Szeider, Stefan
ACM Transactions on Computational Logic, volume 18, number 3, pages Art. 21, 46, 2017.
[doi] [details]
SAT-Encodings for Special Treewidth and Pathwidth
Neha Lodha, Sebastian Ordyniak, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings (Serge Gaspers and Toby Walsh), volume 10491 of Lecture Notes in Computer Science, pages 429-445, 2017, Springer Verlag.
[pdf] [doi] [details]
A SAT Approach to Branchwidth
Neha Lodha and Sebastian Ordyniak and Stefan Szeider
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017 (Carles Sierra), pages 4894-4898, 2017, ijcai.org.
Note: Sister Conference Best Paper Track
[pdf] [doi] [details]
SAT-Encodings for Special Treewidth and Pathwidth
Neha Lodha, Sebastian Ordyniak, Stefan Szeider
2017, Technical report AC-TR-17-012, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
The Treewidth of Proofs
Moritz Müller, Stefan Szeider
2017, Technical report AC-TR-17-010, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
The Treewidth of Proofs
Moritz Müller, Stefan Szeider
Information and Computation, volume 255, pages 147-164, 2017.
[doi] [details]
Long-Distance Q-Resolution with Dependency Schemes
Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings (Serge Gaspers and Toby Walsh), volume 10491 of Lecture Notes in Computer Science, pages 298-313, 2017, Springer Verlag.
[pdf] [doi] [details]
Dependency Learning for QBF
Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
2017, Technical report AC-TR-17-011, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable
M. S. Ramanujan and Stefan Szeider
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pages 3929-3935, 2017.
[pdf] [details]
2016
Positive and Negative Results for Parameterized Compilability
Simone Bova, Ronald de Haan, Neha Lodha, Stefan Szeider
2016, Technical report AC-TR-16-003, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Model Checking Existential Logic on Partially Ordered Sets
Simone Bova, Robert Ganian, Stefan Szeider
ACM Transactions on Computational Logic, volume 17, number 2, 2016.
[doi] [details]
Quantified Conjunctive Queries on Partially Ordered Sets
Simone Bova, Robert Ganian, Stefan Szeider
Theoretical Computer Science, volume 618, pages 72-84, 2016.
[pdf] [doi] [details]
Parameterized Complexity Results for Symbolic Model Checking of Temporal Logics
Ronald de Haan, Stefan Szeider
Proceedings of KR 2016, the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning, Cape Town, South Africa, April 25-29, 2016 (Chitta Baral and James P. Delgrande and Frank Wolter), pages 453-462, 2016, AAAI Press.
[pdf] [details]
Parameterized Complexity Results for Agenda Safety in Judgment Aggregation
Ulle Endriss, Ronald de Haan, Stefan Szeider
2016, Technical report AC-TR-16-005, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
On Existential MSO and its Relation to ETH
Robert Ganian, Ronald de Haan, Iyad Kanj, Stefan Szeider
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) (Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier), volume 58 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1-42:14, 2016, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[pdf] [doi] [details]
Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Robert Ganian, M. S. Ramanujan, Stefan Szeider
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1670-1681, 2016.
[pdf] [doi] [details]
Backdoors to Tractable Valued CSP
Robert Ganian, M.S. Ramanujan, Stefan Szeider
Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings (Michel Rueher), volume 9892 of Lecture Notes in Computer Science, pages 233-250, 2016, Springer Verlag.
[pdf] [[doi]](https://doi.org/10.1007/978-3-319-44953-1 16) [details]
Meta-Kernelization with Structural Parameters
Robert Ganian, Friedrich Slivovsky, Stefan Szeider
Journal of Computer and System Sciences, volume 82, number 2, pages 333-346, 2016.
[pdf] [doi] [details]
Backdoors to q-Horn
Serge Gaspers, Sebastian Ordyniak and M. S. Ramanujan, Saket Saurabh, Stefan Szeider
Algorithmica, volume 74, number 1, pages 540-557, 2016.
[pdf] [doi] [details]
A SAT Approach to Branchwidth
Neha Lodha, Sebastian Ordyniak, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2016 - 19th International Conference, Bordeaux, France, July 5-8, 2016, Proceedings (Nadia Creignou and Daniel Le Berre), volume 9710 of Lecture Notes in Computer Science, pages 179-195, 2016, Springer Verlag.
[pdf] [doi] [details]
Model Counting for CNF Formulas of Bounded Modular Treewidth
Daniël Paulusma, Friedrich Slivovsky and Stefan Szeider
Algorithmica, volume 76, number 1, pages 168-194, 2016.
[pdf] [doi] [details]
Long Distance Q-Resolution with Dependency Schemes
Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2016 - 19th International Conference, Bordeaux, France, July 5-8, 2016, Proceedings (Nadia Creignou and Daniel Le Berre), volume 9710 of Lecture Notes in Computer Science, pages 500-518, 2016, Springer Verlag.
[pdf] [doi] [details]
Soundness of Q-resolution with dependency schemes
Friedrich Slivovsky and Stefan Szeider
Theoretical Computer Science, volume 612, pages 83-101, 2016.
[pdf] [doi] [details]
Quantifier reordering for QBF
Slivovsky, Friedrich, Szeider, Stefan
Journal of Automated Reasoning, volume 56, number 4, pages 459-477, 2016.
[pdf] [doi] [details]
2015
A complete parameterized complexity analysis of bounded planning
Bäckström, Christer, Jonsson, Peter, Ordyniak, Sebastian, Szeider, Stefan
Journal of Computer and System Sciences, volume 81, number 7, pages 1311-1332, 2015.
[pdf] [doi] [details]
On the Subexponential-Time Complexity of CSP
Ronald de Haan, Iyad A. Kanj, Stefan Szeider
Journal of Artificial Intelligence Research, volume 52, pages 203-234, 2015.
[pdf] [doi] [details]
Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP
Ronald de Haan and Stefan Szeider
SOFSEM 2015: Theory and Practice of Computer Science - 41st International Conference on Current Trends in Theory and Practice of Computer Science, Pec pod Sněžkou, Czech Republic, January 24-29, 2015. Proceedings, volume 8939 of Lecture Notes in Computer Science, pages 217-229, 1 2015, Springer Verlag.
[pdf] [doi] [details]
Parameterized Complexity Results for Symbolic Model Checking of Temporal Logics
Ronald de Haan, Stefan Szeider
2015, Technical report AC-TR-15-002, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP
Ronald de Haan, Stefan Szeider
2015, Technical report AC-TR-15-009, Algorithms and Complexity Group, TU Wien.
[pdf] [details]
Solving Problems on Graphs of High Rank-Width
Eduard Eiben, Robert Ganian, Stefan Szeider
Algorithms and Data Structures Symposium (WADS 2015), August 5-7, 2015, University of Victoria, BC, Canada, pages 314-326, 2015, Springer Verlag.
[pdf] [doi] [details]
Meta-Kernelization using Well-Structured Modulators
Eduard Eiben, Robert Ganian, Stefan Szeider
Parameterized and Exact Computation - 10th International Symposium, IPEC 2014, Patras, Greece, September 16-18, 2015. Revised Selected Papers (Thore Husfeldt and Iyad A. Kanj), volume 43 of LIPIcs, pages 114-126, 2015.
[pdf] [doi] [details]
Parameterized Complexity Results for Agenda Safety in Judgment Aggregation
Ulle Endriss, Ronald de Haan, Stefan Szeider
Proceedings of AAMAS 2015, the 14th International Conference on Autonomous Agents and Multiagent Systems (Gerhard Weiss and Pinar Yolum and Rafael H. Bordini and Edith Elkind), pages 127-136, 2015, IFAAMAS/ACM.
[pdf] [details]
Backdoors to Tractable Answer Set Programming
Johannes Klaus Fichte and Stefan Szeider
Artificial Intelligence, volume 220, pages 64-103, 3 2015.
[doi] [details]
Backdoors to Normality for Disjunctive Logic Programs
Johannes Klaus Fichte, Stefan Szeider
ACM Transactions on Computational Logic, volume 17, number 1, 2015.
[doi] [details]
Algorithmic Applications of Tree-Cut Width
Robert Ganian, Eun Jung Kim, Stefan Szeider
Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, volume 9235 of Lecture Notes in Computer Science, pages 348-360, 2015, Springer Verlag.
[pdf] [doi] [details]
Community Structure Inspired Algorithms for SAT and #SAT
Robert Ganian, Stefan Szeider
18th International Conference on Theory and Applications of Satisfiability Testing (SAT 2015), September 24-27, 2015, Austin, Texas (Marijn Heule and Sean Weaver), pages 223-237, 2015, Springer Verlag.
[pdf] [doi] [details]
On finding optimal polytrees
Serge Gaspers and Mikko Koivisto and Mathieu Liedloff and Sebastian Ordyniak and Stefan Szeider
Theoretical Computer Science, volume 592, pages 49-58, 2015.
[pdf] [doi] [details]
A SAT Approach to Clique-Width
Marijn Heule and Stefan Szeider
ACM Transactions on Computational Logic, volume 16, number 3, pages 24, 2015.
[pdf] [doi] [details]
Parameterized and subexponential-time complexity of satisfiability problems and applications
Iyad A. Kanj and Stefan Szeider
Theoretical Computer Science, volume 607, pages 282-295, 2015.
[pdf] [doi] [details]
2014
Model checking existential logic on partially ordered sets
Simone Bova, Robert Ganian, Stefan Szeider
Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS ‘14, Vienna, Austria, July 14 - 18, 2014 (Thomas A. Henzinger and Dale Miller), pages 21:1-21:10, 2014, ACM.
[pdf] [doi] [details]
Quantified Conjunctive Queries on Partially Ordered Sets
Simone Bova, Robert Ganian, Stefan Szeider
Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers (Marek Cygan and Pinar Heggernes), volume 8894 of Lecture Notes in Computer Science, pages 122-134, 2014, Springer Verlag.
[pdf] [doi] [details]
Small Unsatisfiable Subsets in Constraint Satisfaction
Ronald de Haan and Iyad A. Kanj and Stefan Szeider
26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014, Limassol, Cyprus, November 10-12, 2014, pages 429-436, 2014, IEEE.
[pdf] [doi] [details]
Subexponential Time Complexity of CSP with Global Constraints
Ronald de Haan, Iyad A. Kanj, Stefan Szeider
Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Lyon, France, September 8-12, 2014. Proceedings (Barry O’Sullivan), volume 8656 of Lecture Notes in Computer Science, pages 272-288, 2014, Springer Verlag.
[pdf] [doi] [details]
The Parameterized Complexity of Reasoning Problems Beyond NP
de Haan, Ronald, Stefan Szeider
Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014 (Chitta Baral and Giuseppe De Giacomo and Thomas Eiter), pages 82-91, 2014, AAAI Press.
[pdf] [details]
Fixed-Parameter Tractable Reductions to SAT
de Haan, Ronald and Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2014 - 17th International Conference, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17, 2014. Proceedings (Uwe Egly and Carsten Sinz), volume 8561 of Lecture Notes in Computer Science, pages 85-102, 2014, Springer Verlag.
[pdf] [doi] [details]
Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
de Haan, Ronald and Stefan Szeider
2014, Technical report TR14-143, Electronic Colloquium on Computational Complexity (ECCC).
[pdf] [details]
Parameterized Complexity Results for Agenda Safety in Judgment Aggregation
Endriss, Ulle, de Haan, Ronald and Stefan Szeider
Proceedings of ComSoc'14, Fifth International Workshop on Computational Social Choice Pittsburgh, Pennsylvania, June 23-25, 2014, pages 127-136, 2014.
[pdf] [details]
Backdoors into Heterogeneous Classes of SAT and CSP
Serge Gaspers and Neeldhara Misra and Sebastian Ordyniak and Stefan Szeider and Stanislav Zivny
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27-31, 2014, Québec City, Québec, Canada. (Carla E. Brodley and Peter Stone), pages 2652-2658, 2014, AAAI Press.
[details]
Guarantees and limits of preprocessing in constraint satisfaction and reasoning
Gaspers, Serge, Szeider, Stefan
Artificial Intelligence, volume 216, pages 1-19, 2014.
[doi] [details]
Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications
Iyad A. Kanj, Stefan Szeider
Combinatorial Optimization and Applications - 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings (Zhao Zhang and Lidong Wu and Wen Xu and Ding-Zhu Du), volume 8881 of Lecture Notes in Computer Science, pages 637-651, 2014, Springer Verlag.
[pdf] [doi] [details]
Tractable answer-set programming with weight constraints: bounded treewidth is not enough
Reinhard Pichler and Stefan Rümmele and Stefan Szeider and Stefan Woltran
Theory Pract. Log. Program., volume 14, number 2, pages 141-164, 2014.
[doi] [details]
Variable Dependencies and Q-Resolution
Friedrich Slivovsky and Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2014 - 17th International Conference, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17, 2014. Proceedings (Carsten Sinz and Uwe Egly), volume 8561 of Lecture Notes in Computer Science, pages 269-284, 2014, Springer Verlag.
[doi] [details]
2013
Parameterized Complexity and Kernel Bounds for Hard Planning Problems
Christer Bäckström, Peter Jonsson and Sebastian Ordyniak, Stefan Szeider
Algorithms and Complexity, 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings (Paul G. Spirakis and Maria J. Serna), volume 7878 of Lecture Notes in Computer Science, pages 13-24, 2013, Springer Verlag.
[doi] [details]
Local Backbones
Ronald de Haan, Iyad A. Kanj, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2013 - 16th International Conference, Helsinki, Finland, July 8-12, 2013. Proceedings (Matti Järvisalo and Allen Van Gelder), volume 7962 of Lecture Notes in Computer Science, pages 377-393, 2013, Springer Verlag.
[pdf] [doi] [details]
Parameterized Complexity Results for Plan Reuse
Ronald de Haan, Anna Roubickova, 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), pages 224-231, 2013, The AAAI Press.
[pdf] [details]
Backdoors to Normality for Disjunctive Logic Programs
Johannes Klaus Fichte, 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), pages 320-337, 2013, The AAAI Press.
[details]
Backdoors to q-Horn
Serge Gaspers, Sebastian Ordyniak and M. S. Ramanujan, Saket Saurabh, Stefan Szeider
30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany (Natacha Portier and Thomas Wilke), volume 20 of LIPIcs, pages 67-79, 2013, Leibniz-Zentrum fuer Informatik.
[doi] [details]
Strong Backdoors to Bounded Treewidth SAT
Serge Gaspers and Stefan Szeider
54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 489-498, 2013, IEEE Computer Society.
[doi] [details]
A SAT Approach to Clique-Width
Marijn Heule, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2013 - 16th International Conference, Helsinki, Finland, July 8-12, 2013. Proceedings (Matti Järvisalo and Allen Van Gelder), volume 7962 of Lecture Notes in Computer Science, pages 318-334, 2013, Springer Verlag.
[doi] [details]
On the Subexponential Time Complexity of CSP
Iyad Kanj, 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), pages 459-465, 2013, The AAAI Press.
[details]
The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation
Eun Jung Kim and Sebastian Ordyniak and Stefan Szeider
Theory and Applications of Formal Argumentation - Second International Workshop, TAFA 2013, Beijing, China, August 3-5, 2013, Revised Selected papers (Elizabeth Black and Sanjay Modgil and Nir Oren), volume 8306 of Lecture Notes in Computer Science, pages 158-175, 2013, Springer Verlag.
[doi] [details]
Upper and Lower Bounds for Weak Backdoor Set Detection
Neeldhara Misra, Sebastian Ordyniak, Venkatesh Raman, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2013 - 16th International Conference, Helsinki, Finland, July 8-12, 2013. Proceedings (Matti Järvisalo and Allen Van Gelder), volume 7962 of Lecture Notes in Computer Science, pages 394-402, 2013, Springer Verlag.
[doi] [details]
Revisiting Space in Proof Complexity: Treewidth and Pathwidth
Moritz Müller, Stefan Szeider
Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings (Krishnendu Chatterjee and Jiri Sgall), volume 8087 of Lecture Notes in Computer Science, pages 704-716, 2013, Springer Verlag.
[doi] [details]
Satisfiability of acyclic and almost acyclic CNF formulas
Sebastian Ordyniak, Daniël Paulusma and Stefan Szeider
Theoretical Computer Science, volume 481, pages 85-99, 2013.
[doi] [details]
Parameterized Complexity Results for Exact Bayesian Network Structure Learning
Sebastian Ordyniak, Stefan Szeider
Journal of Artificial Intelligence Research, volume 46, pages 263-302, 2013.
[doi] [details]
Model Counting for CNF Formulas of Bounded Modular Treewidth
Daniël Paulusma, Friedrich Slivovsky and Stefan Szeider
30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany (Natacha Portier and Thomas Wilke), volume 20 of LIPIcs, pages 55-66, 2013, Leibniz-Zentrum fuer Informatik.
[doi] [details]
Backdoors to Abduction
Andreas Pfandler, Stefan Rümmele, Stefan Szeider
Proceedings of IJCAI 2013, the 23th International Joint Conference on Artificial Intelligence, August 3-9, 2013, Beijing, China, 2013.
[details]
Model Counting for Formulas of Bounded Clique-Width
Friedrich Slivovsky and Stefan Szeider
Algorithms and Computation - 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings (Leizhen Cai and Siu-Wing Cheng and Tak Wah Lam), volume 8283 of Lecture Notes in Computer Science, pages 677-687, 2013, Springer Verlag.
[doi] [details]
The Parameterized Complexity of Constraint Satisfaction and Reasoning
Stefan Szeider
Applications of Declarative Programming and Knowledge Management - 19th International Conference, INAP 2011, and 25th Workshop on Logic Programming, WLP 2011, Vienna, Austria, September 28-30, 2011, Revised Selected Papers (Hans Tompits and Salvador Abreu and Johannes Oetsch and Jörg Pührer and Dietmar Seipel and Masanobu Umeda and Armin Wolf), volume 7773 of Lecture Notes in Computer Science, pages 27-37, 2013, Springer Verlag.
[[doi]](https://doi.org/10.1007/978-3-642-41524-1 2) [details]
Capturing Structure in Hard Combinatorial Problems
Stefan Szeider
2013 IEEE 25th International Conference on Tools with Artificial Intelligence, Herndon, VA, USA, November 4-6, 2013, pages 897-898, 2013.
Note: invited keynote talk
[doi] [details]
2012
The Complexity of Planning Revisited - A Parameterized Analysis
Christer Bäckström, Yue Chen, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider
Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada (Jörg Hoffmann and Bart Selman), 2012, AAAI Press.
[details]
Augmenting tractable fragments of abstract argumentation
Dvorák, Sebastian Ordyniak and Stefan Szeider
Artificial Intelligence, volume 186, pages 157-173, 2012.
[doi] [details]
Abstract Argumentation via Monadic Second Order Logic
Wolfgang Dvorák, Stefan Szeider, Stefan Woltran
Scalable Uncertainty Management - 6th International Conference, SUM 2012, Marburg, Germany, September 17-19, 2012. Proceedings (Eyke Hüllermeier and Sebastian Link and Thomas Fober and Bernhard Seeger), volume 7520 of Lecture Notes in Computer Science, pages 85-98, 2012, Springer Verlag.
[doi] [details]
Backdoors to Tractable Answer-Set Programming
Johannes Klaus Fichte, Stefan Szeider
2012, Technical report 1104.2788, Arxiv.org.
Note: Extended and updated version of a paper that appeared in the proceedings of IJCAI 2011, the 22nd International Joint Conference on Artificial Intelligence
[details]
k-Gap Interval Graphs
Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Karol Suchan, Stefan Szeider and Erik Jan van Leeuwen, Martin Vatshelle, Yngve Villanger
LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012. Proceedings (David Fernández-Baca), volume 7256 of Lecture Notes in Computer Science, pages 350-361, 2012, Springer Verlag.
[doi] [details]
Don’t Be Strict in Local Search!
Serge Gaspers, Eun Jung Kim, Sebastian Ordyniak, Saket Saurabh, Stefan Szeider
Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada (Jörg Hoffmann and Bart Selman), 2012, AAAI Press.
[details]
On Finding Optimal Polytrees
Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, Stefan Szeider
Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada (Jörg Hoffmann and Bart Selman), 2012, AAAI Press.
[details]
Backdoors to Satisfaction
Serge Gaspers, Stefan Szeider
The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday (Hans L. Bodlaender and Rod Downey and Fedor V. Fomin and Dániel Marx), volume 7370 of Lecture Notes in Computer Science, pages 287-317, 2012, Springer Verlag.
[doi] [details]
Backdoors to Acyclic SAT
Serge Gaspers, Stefan Szeider
Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I (Artur Czumaj and Kurt Mehlhorn and Andrew M. Pitts and Roger Wattenhofer), volume 7391 of Lecture Notes in Computer Science, pages 363-374, 2012, Springer Verlag.
[doi] [details]
Strong Backdoors to Nested Satisfiability
Serge Gaspers, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2012 - 15th International Conference, Trento, Italy, June 17-20, 2012. Proceedings (Alessandro Cimatti and Roberto Sebastiani), volume 7317 of Lecture Notes in Computer Science, pages 72-85, 2012, Springer Verlag.
[doi] [details]
Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming
Gregory Gutin, Eun Jung Kim, Arezou Soleimanfallah, Stefan Szeider, Anders Yeo
Algorithmica, volume 64, number 1, pages 112-125, 2012.
[doi] [details]
Editing graphs to satisfy degree constraints: a parameterized approach
Mathieson, Luke, Szeider, Stefan
Journal of Computer and System Sciences, volume 78, number 1, pages 179-191, 2012.
[doi] [details]
Computing Resolution-Path Dependencies in Linear Time
Friedrich Slivovsky, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2012 - 15th International Conference, Trento, Italy, June 17-20, 2012. Proceedings (Alessandro Cimatti and Roberto Sebastiani), volume 7317 of Lecture Notes in Computer Science, pages 58-71, 2012, Springer Verlag.
[doi] [details]
On graph contractions and induced minors
van ’t Hof, Pim, Kami\ʼnski, Marcin and Paulusma, Daniël, Szeider, Stefan and Thilikos, Dimitrios M.
Discr. Appl. Math., volume 160, number 6, pages 799-809, 2012.
[doi] [details]
2011
Solving MAX-r-SAT above a tight lower bound
Alon, Noga, Gutin, Gregory, Kim, Eun Jung, Szeider, Stefan, Yeo, Anders
Algorithmica, volume 61, number 3, pages 638-655, 2011.
[doi] [details]
Parameterized Proof Complexity
Stefan S. Dantchev and Barnaby Martin and Stefan Szeider
Computational Complexity, volume 20, number 1, pages 51-85, 2011.
[doi] [details]
On the complexity of some colorful problems parameterized by treewidth
Fellows, Michael R., Fomin, Fedor V., Lokshtanov, Daniel and Rosamond, Frances, Saurabh, Saket, Szeider, Stefan and Thomassen, Carsten
Information and Computation, volume 209, number 2, pages 143-153, 2011.
[details]
Backdoors to Tractable Answer-Set Programming
Johannes Klaus Fichte, Stefan Szeider
Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 (Toby Walsh), pages 863-868, 2011, AAAI Press/IJCAI.
[details]
Backdoors to Acyclic SAT
Serge Gaspers, Stefan Szeider
10 2011, Technical report 1110.6384, Arxiv.org.
[details]
Backdoors to Satisfaction
Serge Gaspers, Stefan Szeider
10 2011, Technical report 1110.6387, Arxiv.org.
[details]
The Parameterized Complexity of Local Consistency
Serge Gaspers, Stefan Szeider
Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP 2011) (Jimmy Ho-Man Lee), volume 6876 of Lecture Notes in Computer Science, pages 302-316, 2011, Springer Verlag.
[pdf] [details]
Kernels for Global Constraints
Serge Gaspers and Stefan Szeider
IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011 (Toby Walsh), pages 540-545, 2011, IJCAI/AAAI.
[details]
A probabilistic approach to problems parameterized above or below tight bounds
Gregory Gutin and Eun Jung Kim and Stefan Szeider and Anders Yeo
Journal of Computer and System Sciences, volume 77, number 2, pages 422-429, 2011.
[pdf] [doi] [details]
Algorithms and Complexity Results for Persuasive Argumentation
Eun Jung Kim, Sebastian Ordyniak, Stefan Szeider
Artificial Intelligence, volume 175, pages 1722-1736, 2011.
[details]
Satisfiability of Acyclic and almost Acyclic CNF Formulas (II)
Sebastian Ordyniak, Daniël Paulusma, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2011 - 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011. Proceedings (Karem A. Sakallah and Laurent Simon), volume 6695 of Lecture Notes in Computer Science, pages 47-60, 2011, Springer Verlag.
[doi] [details]
Augmenting Tractable Fragments of Abstract Argumentation
Sebastian Ordyniak, Stefan Szeider
Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 (Toby Walsh), pages 1033-1038, 2011, AAAI Press/IJCAI.
[details]
Tractable cases of the extended global cardinality constraint
Marko Samer and Stefan Szeider
Constraints, volume 16, number 1, pages 1-24, 2011.
[doi] [details]
Monadic Second Order Logic on Graphs with Local Cardinality Constraints
Stefan Szeider
ACM Transactions on Computational Logic, volume 12, number 2, pages article 12, 2011.
[doi] [details]
Limits of Preprocessing
Stefan Szeider
Proceedings of the Twenty-Fifth Conference on Artificial Intelligence, AAAI 2011, pages 93-98, 2011, AAAI Press, Menlo Park, California.
[pdf] [details]
The parameterized complexity of k-flip local search for SAT and MAX SAT
Szeider, Stefan
Discrete Optim., volume 8, number 1, pages 139-145, 2011.
[details]
2010
Solving MAX-r-SAT Above a Tight Lower Bound
Noga Alon and Gregory Gutin and Eun Jung Kim and Stefan Szeider and Anders Yeo
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010 (Moses Charikar), pages 511-517, 2010, SIAM.
[doi] [details]
Reasoning in Argumentation Frameworks of Bounded Clique-Width
Dvorák, Stefan Szeider and Stefan Woltran
Computational Models of Argumentation, Proceedings of COMMA 2010 (Pietro Baroni and Federico Cerutti and Massimiliano Giacomin and Guillermo R. Simari), volume 216 of Frontiers in Artificial Intelligence and Applications, pages 219-230, 2010.
[details]
Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming
Gregory Gutin and Eun Jung Kim and Arezou Soleimanfallah and Stefan Szeider and Anders Yeo
Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings (Venkatesh Raman and Saket Saurabh), volume 6478 of Lecture Notes in Computer Science, pages 158-169, 2010, Springer Verlag.
[doi] [details]
On Contracting Graphs to Fixed Pattern Graphs
Pim van ’t Hof and Marcin Kaminski and Daniël Paulusma and Stefan Szeider and Dimitrios M. Thilikos
SOFSEM 2010: Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlýn, Czech Republic, January 23-29, 2010. Proceedings (Jan van Leeuwen and Anca Muscholl and David Peleg and Jaroslav Pokorný and Bernhard Rumpe), volume 5901 of Lecture Notes in Computer Science, pages 503-514, 2010, Springer Verlag.
[doi] [details]
Algorithms and Complexity Results for Persuasive Argumentation
Eun Jung Kim, Sebastian Ordyniak, Stefan Szeider
Computational Models of Argumentation, Proceedings of COMMA 2010 (Pietro Baroni and Federico Cerutti and Massimiliano Giacomin and Guillermo R. Simari), volume 216 of Frontiers in Artificial Intelligence and Applications, pages 311-322, 2010.
[details]
Satisfiability of Acyclic and Almost Acyclic CNF Formulas
Sebastian Ordyniak and Daniël Paulusma and Stefan Szeider
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India (Kamal Lodaya and Meena Mahajan), volume 8 of LIPIcs, pages 84-95, 2010, Leibniz-Zentrum fuer Informatik.
[details]
Algorithms and Complexity Results for Exact Bayesian Structure Learning
Sebastian Ordyniak, 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), 2010, AUAI Press, Corvallis, Oregon.
[details]
Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth Is not Enough
Reinhard Pichler and Stefan Rümmele and Stefan Szeider and Stefan Woltran
Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, KR 2010, Toronto, Ontario, Canada, May 9-13, 2010 (Fangzhen Lin and Ulrike Sattler and Miroslaw Truszczynski), 2010, AAAI Press.
[details]
Algorithms for propositional model counting
Samer, Marko, Szeider, Stefan
J. Discrete Algorithms, volume 8, number 1, pages 50-64, 2010.
[pdf] [doi] [details]
Constraint satisfaction with bounded treewidth revisited
Marko Samer, Stefan Szeider
Journal of Computer and System Sciences, volume 76, number 2, pages 103-114, 2010.
[pdf] [details]
2009
Clique-width is NP-complete
Fellows, Michael R., Rosamond, Frances A., Rotics, Udi and Szeider, Stefan
SIAM J. Discrete Math., volume 23, number 2, pages 909-939, 2009.
[pdf] [details]
Covering graphs with few complete bipartite subgraphs
Herbert Fleischner and Egbert Mujuni and Daniël Paulusma and Stefan Szeider
Theoretical Computer Science, volume 410, number 21-23, pages 2045-2053, 2009.
[pdf] [doi] [details]
A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
Gregory Gutin, Eun Jung Kim, Stefan Szeider and Anders Yeo
Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers (Jianer Chen and Fedor V. Fomin), volume 5917 of Lecture Notes in Computer Science, pages 234-245, 2009, Springer Verlag.
[details]
Backdoor sets of quantified Boolean formulas
Samer, Marko, Szeider, Stefan
Journal of Automated Reasoning, volume 42, number 1, pages 77-97, 2009.
[pdf] [doi] [details]
The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2009, 12th International Conference, SAT 2009, Swansea, UK, June 30 - July 3, 2009. Proceedings (Oliver Kullmann), volume 5584 of Lecture Notes in Computer Science, pages 276-283, 2009, Springer Verlag.
[details]
Matched Formulas and Backdoor Sets
Stefan Szeider
J on Satisfiability, Boolean Modeling and Computation, volume 6, pages 1-12, 2009.
[pdf] [details]
2008
Fixed-parameter algorithms for artificial intelligence, constraint satisfaction, and database problems
Georg Gottlob, Stefan Szeider
The Computer Journal, volume 51, number 3, pages 303-325, 2008.
Note: Survey paper
[pdf] [doi] [details]
Fixed-parameter complexity of minimum profile problems
Gutin, Gregory, Szeider, Stefan, Yeo, Anders
Algorithmica, volume 52, number 2, pages 133-152, 2008.
[pdf] [details]
The Parameterized Complexity of Regular Subgraph Problems and Generalizations
Luke Mathieson, Stefan Szeider
Proceedings of CATS 2008, Computing: The Australasian Theory Symposium, University of Wollongong, New South Wales, Australia, January 22-25, 2008 (J. Harland and P. Manyem), volume 77 of Conferences in Research and Practice in Information Technology, pages 79-86, 2008, Australian Computer Society.
[details]
Parameterized Graph Editing with Chosen Vertex Degrees
Luke Mathieson and Stefan Szeider
Combinatorial Optimization and Applications, Second International Conference, COCOA 2008, St. John’s, NL, Canada, August 21-24, 2008. Proceedings (Boting Yang and Ding-Zhu Du and Cao An Wang), volume 5165 of Lecture Notes in Computer Science, pages 13-22, 2008, Springer Verlag.
[doi] [details]
Tractable Cases of the Extended Global Cardinality Constraint
Marko Samer, Stefan Szeider
Proceedings of CATS 2008, Computing: The Australasian Theory Symposium, University of Wollongong, New South Wales, Australia, January 22-25, 2008 (J. Harland and P. Manyem), volume 77 of Conferences in Research and Practice in Information Technology, pages 67-74, 2008, Australian Computer Society.
[details]
Backdoor Trees
Marko Samer, Stefan Szeider
AAAI 08, Twenty-Third Conference on Artificial Intelligence, Chicago, Illinois, July 13-17, 2008, pages 363-368, 2008, AAAI Press.
[pdf] [details]
Monadic Second Order Logic on Graphs with Local Cardinality Constraints
Stefan Szeider
Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings, volume 5162 of Lecture Notes in Computer Science, pages 601-612, 2008, Springer Verlag.
[details]
Parameterized SAT
Stefan Szeider
Chapter in Encyclopedia of Algorithms (Ming-Yang Kao), 2008, Springer Verlag.
[details]
Not So Easy Problems For Tree Decomposable Graphs (invited talk)
Stefan Szeider
ICDM 2008, International Conference on Discrete Mathematics, June 6-10, 2008, Mysore, India, Proceedings, pages 161-171, 2008.
[pdf] [details]
2007
Parameterized Proof Complexity
Stefan Dantchev, Barnaby Martin, Stefan Szeider
Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, pages 150-160, 2007, IEEE Press.
[doi] [details]
On the Complexity of Some Colorful Problems Parameterized by Treewidth
Michael R. Fellows and Fedor V. Fomin and Daniel Lokshtanov and Frances A. Rosamond and Saket Saurabh and Stefan Szeider and Carsten Thomassen
Proceedings of COCOA 2007, Combinatorial Optimization and Applications, First International Conference, Xi’an, China, August 14-16, 2007, volume 4616 of Lecture Notes in Computer Science, pages 366-377, 2007, Springer Verlag.
[details]
Covering Graphs with Few Complete Bipartite Subgraphs
Herbert Fleischner and Egbert Mujuni and Daniël Paulusma and Stefan Szeider
FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 27th International Conference, New Delhi, India, December 12-14, 2007, Proceedings (Vikraman Arvind and Sanjiva Prasad), volume 4855 of Lecture Notes in Computer Science, pages 340-351, 2007, Springer Verlag.
[doi] [details]
The Linear Arrangement Problem Parameterized Above Guaranteed Value
Gregory Gutin, Arash Rafiey, Stefan Szeider and Anders Yeo
Theory Comput. Syst., volume 41, pages 521-538, 2007.
[pdf] [details]
Solving #SAT using Vertex Covers
Naomi Nishimura, Prabhakar Ragde, Stefan Szeider
Acta Informatica, volume 44, number 7-8, pages 509-523, 2007.
[pdf] [details]
Backdoor Sets of Quantified Boolean Formulas
Marko Samer, Stefan Szeider
Proceedings of SAT 2007, Tenth International Conference on Theory and Applications of Satisfiability Testing, May 28-31, 2007, Lisbon, Portugal, (J. Marques-Silva and K. A. Sakallah), volume 4501 of Lecture Notes in Computer Science, pages 230-243, 2007.
[details]
Algorithms for Propositional Model Counting
Marko Samer, Stefan Szeider
Proceedings of LPAR 2007, 14th International Conference on Logic for Programming, Artificial Intelligence and Reasoning, October 15-19, 2007 Yerevan, Armenia, volume 4790 of Lecture Notes in Computer Science, pages 484-498, 2007, Springer Verlag.
[details]
Matched Formulas and Backdoor Sets
Stefan Szeider
Proceedings of SAT 2007, Tenth International Conference on Theory and Applications of Satisfiability Testing, May 28-31, 2007, Lisbon, Portugal, (J. Marques-Silva and K. A. Sakallah), volume 4501 of Lecture Notes in Computer Science, pages 94-99, 2007.
[details]
Without Loss of Generality - Symmetric Reasoning for Resolution Systems (Invited Talk)
Stefan Szeider
Proceedings of SymCon'07, Seventh International Workshop on Symmetry and Constraint Satisfaction Problems, satellite workshop of CP 2007, September 23, 2007, Providence, RI, USA (B. Benhamou), pages 5-8, 2007.
[pdf] [details]
2006
Clique-width Minimization is NP-hard
Michael R. Fellows, Frances A. Rosamond, Udi Rotics and Stefan Szeider
Proceedings of STOC 2006; the 38th ACM Symposium on Theory of Computing, Seattle, Washington, USA, pages 354-362, 2006, ACM.
[doi] [details]
On Finding Short Resolution Refutations and Small Unsatisfiable Subsets
Michael R. Fellows, Stefan Szeider, Graham Wrightson
Theoretical Computer Science, volume 351, number 3, pages 351-359, 2006.
[pdf] [details]
The Linear Arrangement Problem Parameterized Above Guaranteed Value
Gregory Gutin and Arash Rafiey and Stefan Szeider and Anders Yeo
Algorithms and Complexity, 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings (Tiziana Calamoneri and Irene Finocchi and Giuseppe F. Italiano), volume 3998 of Lecture Notes in Computer Science, pages 356-367, 2006, Springer Verlag.
[doi] [details]
Fixed-Parameter Complexity of Minimum Profile Problems
Gregory Gutin, Anders Yeo, Stefan Szeider
Proceedings of IWPEC 2006, 2nd International Workshop on Parameterized and Exact Computation, volume 4169 of Lecture Notes in Computer Science, pages 60-71, 2006, Springer Verlag.
[details]
A note on unsatisfiable k-CNF formulas with few occurrences per variable
Shlomo Hoory, Stefan Szeider
SIAM J. Discrete Math., volume 20, number 2, pages 523-528, 2006.
[pdf] [details]
Solving #SAT using Vertex Covers
Naomi Nishimura, Prabhakar Ragde, Stefan Szeider
Proceedings of SAT 2006, Ninth International Conference on Theory and Applications of Satisfiability Testing, August 12-15, 2006, Seattle, Washington, USA, volume 4121 of Lecture Notes in Computer Science, pages 396-409, 2006.
[details]
Constraint satisfaction with bounded treewidth revisited
Marko Samer, Stefan Szeider
Proceedings of CP 2006 , Twelfth International Conference on Principles and Practice of Constraint Programming, September 24-29, 2006, Nantes, France, volume 4204 of Lecture Notes in Computer Science, pages 499-513, 2006.
Note: Full version appeared in Constraints
[details]
2005
On Edge-Colored Graphs Covered by Properly Colored Cycles
Herbert Fleischner, Stefan Szeider
Graphs and Combinatorics, volume 21, number 3, pages 301-206, 2005.
[pdf] [details]
Computing unsatisfiable k-SAT instances with few occurrences per variable
Hoory, Shlomo, Szeider, Stefan
Theoretical Computer Science, volume 337, number 1-3, pages 347-359, 2005.
Note: Supplementary material is available at r̆lhttps://www.ac.tuwien.ac.at/files/pub/HoorySzeider05.tar.gz
[pdf] [details]
Generalizations of matched CNF formulas
Stefan Szeider
Ann. Math. Artif. Intell., volume 43, number 1-4, pages 223-238, 2005.
[pdf] [details]
Backdoor Sets for DLL Subsolvers
Stefan Szeider
Journal of Automated Reasoning, volume 35, number 1-3, pages 73-88, 2005.
Note: 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
[pdf] [details]
The Complexity of Resolution with Generalized Symmetry Rules
Stefan Szeider
Theory Comput. Syst., volume 38, number 2, pages 171-188, 2005.
[pdf] [details]
2004
On Finding Short Resolution Refutations and Small Unsatisfiable Subsets
Michael R. Fellows, Stefan Szeider, Graham Wrightson
1st International Workshop on Parameterized and Exact Computation (IWPEC 2004) (Rod Downey and Michael Fellows and Frank Dehne), volume 3162 of Lecture Notes in Computer Science, pages 223-234, 2004, Springer.
[details]
Computing Unsatisfiable k-SAT Instances with Few Occurrences per Variable
Shlomo Hoory, Stefan Szeider
SAT 2004 - The Seventh International Conference on Theory and Applications of Satisfiability Testing, 10-13 May 2004, Vancouver, BC, Canada, Online Proceedings, 2004.
[details]
Detecting Backdoor Sets with Respect to Horn and Binary Clauses
Naomi Nishimura, Prabhakar Ragde, Stefan Szeider
Proceedings of SAT 2004 (Seventh International Conference on Theory and Applications of Satisfiability Testing, 10-13 May, 2004, Vancouver, BC, Canada), pages 96-103, 2004.
[pdf] [details]
The Parameterized Complexity of SAT Backdoors
Stefan Szeider
Computing: The Australasian Theory Symposium (CATS 2004) (Mike Atkinson), pages 252-261, 2004.
Note: Informal Proceedings
[details]
On fixed-parameter tractable parameterizations of SAT
Stefan Szeider
Theory and Applications of Satisfiability, 6th International Conference, SAT 2003, Selected and Revised Papers (Enrico Giunchiglia and Armando Tacchella), volume 2919 of Lecture Notes in Computer Science, pages 188-202, 2004, Springer Verlag.
[pdf] [details]
On Theorems Equivalent with Kotzig’s Result on Graphs with Unique 1-Factors
Stefan Szeider
Ars Combinatoria, volume 73, pages 53-64, 2004.
[pdf] [details]
Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
Stefan Szeider
Journal of Computer and System Sciences, volume 69, number 4, pages 656-674, 2004.
[pdf] [doi] [details]
2003
Finding paths in graphs avoiding forbidden transitions
Stefan Szeider
Discr. Appl. Math., volume 126, number 2-3, pages 239-251, 2003.
[pdf] [doi] [details]
Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
Stefan Szeider
2003, Technical report TR03-002, Revision~1, Electronic Colloquium on Computational Complexity (ECCC).
[pdf] [details]
The complexity of resolution with generalized symmetry rules
Stefan Szeider
Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science (STACS'03) (Helmut Alt and Michel Habib), volume 2607 of Lecture Notes in Computer Science, pages 475-486, 2003.
[details]
Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
Stefan Szeider
Proceedings of the 9th International Computing and Combinatorics Conference (COCOON'03) (T. Warnow and B. Zhu), volume 2697 of Lecture Notes in Computer Science, pages 548-558, 2003, Springer Verlag.
[details]
Homomorphisms of Conjunctive Normal Forms
Stefan Szeider
Discr. Appl. Math., volume 130, number 2, pages 351-365, 2003.
[pdf] [details]
2002
Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference
Fleischner, Herbert, Kullmann, Oliver, Szeider, Stefan
Theoretical Computer Science, volume 289, number 1, pages 503-516, 2002.
[pdf] [details]
Generalizations of matched CNF formulas
Stefan Szeider
Proceedings of the Fifth International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2002) Cincinnati, Ohio, USA, May 6-9, 2002 (John Franco), pages 292-307, 5 2002.
[details]
2001
NP-Completeness of Refutability by Literal-Once Resolution
Stefan Szeider
IJCAR 2001, Proceedings of the International Joint Conference on Automated Reasoning (R. Goré and A. Leitsch and T. Nipkow), volume 2083 of Lecture Notes in Artificial Intelligence, pages 168-181, 2001, Springer Verlag.
[details]
Conjunctive Normal Forms with Bounded Deficiency
Stefan Szeider
9 2001, PhD thesis, University of Vienna.
[details]
AC Admin
Website maintainer