Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

SAT Based Local Improvement (Research Project)

Funding organization: Austrian Science Fund (FWF)

Project number: (FWF P 32441)

Project Team

Stefan Szeider (PI)

André Schidler

P.R. Vaidyanathan

Topic

Structural decomposition is one of the most successful approaches to the solution of hard computational problems, such as for probabilistic reasoning and computational medical diagnosis. Finding a suitable structural decomposition is itself a computationally hard problem. In this project we propose to study a new approach to finding structural decompositions. The idea is to use an exact method (in particular one that is based on satisfiability-solvers) to locally improve a heuristically obtained decomposition. Based on this new idea we will develop new algorithms for the decomposition of graphs and hypergraphs as well as for structural Bayesian Network learning. Our new approach bears the potential of achieving better decompositions for instances that are too large to be handled by exact approaches, and it also provides novel applications for satisfiability solver technology.

Publications

26 results
2022
[26]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, Bettina Speckmann, eds.), pages 67–77, 2022, Society for Industrial and Applied Mathematics (SIAM).
[bibtex] [pdf] [doi]
[25]A SAT Attack on Rota’s Basis Conjecture
Markus Kirchweger, Manferd Scheucher, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2022 - 25th International Conference, Proceedings, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[bibtex]
[24]Weighted Model Counting with Twin-Width
Robert Ganian, Filip Pokrývka, Andre Schidler, Kirill Simonov, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2022 - 25th International Conference, Proceedings, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[bibtex]
[23]Tractable Abstract Argumentation via Backdoor-Treewidth
Wolfgang Dvorak, Markus Hecher, Matthias König, Andre Schidler, Stefan Szeider, Stefan Woltran
Proceeding of AAAI-22, the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022, AAAI Press.
Note: to appear
[bibtex]
2021
[22]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
[bibtex] [doi]
[21]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, A. Beygelzimer, K. Nguyen, P.S. Liang, J.W. Vaughan, Y. Dauphin, eds.), pages 17852–17863, 2021.
[bibtex] [pdf]
[20]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.
[bibtex] [pdf]
[19]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, ed.), 2021.
[bibtex] [doi]
[18]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.
[bibtex] [pdf]
[17]Finding the Hardest Formulas for Resolution (Extended Abstract)
Tomás Peitl, Stefan Szeider
Proceeding of IJCAI-21, the 30th International Joint Conference on Artificial Intelligence (Zhi-Hua Zhou, ed.), pages 4814–4818, 2021.
Note: Sister Conferences Best Papers
[bibtex] [doi]
[16]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.
[bibtex] [pdf]
[15]Backdoor DNFs
Sebastian Ordyniak, Andre Schidler, Stefan Szeider
Proceeding of IJCAI-2021, the 30th International Joint Conference on Artificial Intelligence (Zhi-Hua Zhou, ed.), pages 1403–1409, 2021.
[bibtex] [doi]
[14]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, ed.), pages 39:1–-39:17, 2021, Dagstuhl Publishing.
[bibtex] [pdf] [doi]
[13]The Parameterized Complexity of Clustering Incomplete Data
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider
Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 7296–7304, 2021, AAAI Press.
[bibtex] [pdf]
2020
[12]On Existential MSO and its Relation to ETH
Robert Ganian, Ronald de Haan, Iyad Kanj, Stefan Szeider
ACM Transactions on Computation Theory, volume 12, number 4, pages 22:1–22:32, 2020.
[bibtex]
[11]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, ed.), volume 12333 of Lecture Notes in Computer Science, pages 478–495, 2020, Springer Verlag.
[bibtex] [pdf] [doi]
[10]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, Martina Seidl, eds.), volume 12178 of Lecture Notes in Computer Science, pages 267–276, 2020, Springer Verlag.
[bibtex] [pdf]
[9]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, Martina Seidl, eds.), volume 12178 of Lecture Notes in Computer Science, pages 412–428, 2020, Springer Verlag.
[bibtex] [pdf]
[8]Computing Optimal Hypertree Decompositions
André Schidler, Stefan Szeider
Proceedings of ALENEX 2020, the 22nd SIAM Symposium on Algorithm Engineering and Experiments (Guy Blelloch, Irene Finocchi, eds.), pages 1–11, 2020, Society for Industrial and Applied Mathematics (SIAM).
[bibtex] [pdf]
[7]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, ed.), volume 12333 of Lecture Notes in Computer Science, pages 514–530, 2020, Springer Verlag.
Note: Best Paper Award
[bibtex] [pdf]
[6]Formalizing Graph Trail Properties in Isabelle/HOL
Laura Kovács, Hanna Lachnitt, Stefan Szeider
Intelligent Computer Mathematics - 13th International Conference, CICM 2020, Bertinoro, Italy, July 26-31, 2020, Proceedings (Christoph Benzmüller, Bruce R. Miller, eds.), volume 12236 of Lecture Notes in Computer Science, pages 190–205, 2020, Springer Verlag.
[bibtex] [pdf]
[5]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.
[bibtex] [pdf] [doi]
[4]Fixed-Parameter Tractability of Dependency QBF with Structural Parameters
Robert Ganian, Tomás Peitl, Friedrich Slivovsky, Stefan Szeider
Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020 (Diego Calvanese, Esra Erdem, Michael Thielscher, eds.), pages 392–402, 2020.
[bibtex] [pdf]
[3]On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Dimension
Robert Ganian, Iyad Kanj, Sebastian Ordyniak, 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.
[bibtex] [pdf]
[2]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, ed.), volume 12333 of Lecture Notes in Computer Science, pages 286–303, 2020, Springer Verlag.
[bibtex] [pdf]
[1]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, ed.), volume 12333 of Lecture Notes in Computer Science, pages 267–285, 2020, Springer Verlag.
[bibtex] [pdf]

 

News

  • Best paper award at EvoCOP 2022

    Best paper award at EvoCOP 2022

    2022-05-24
    Jonas Mayerhofer, Markus Kirchweger, Marc Huber, and Günther Raidl received the best paper award for their work A Beam Search …Read More »
  • New PhD: Guangping Li

    New PhD: Guangping Li

    2022-05-13
    Guangping Li successfully defended her PhD thesis “An Algorithmic Study of Practical Map Labeling” on May 13, 2022. Congratulations, Dr. …Read More »
  • Outstanding results for TU Wien students at the 2021 Graph Drawing Contest

    Outstanding results for TU Wien students at the 2021 Graph Drawing Contest

    2021-09-24
    The 28th Annual Graph Drawing Contest, a long running tradition of the graph drawing research community, was held in conjunction …Read More »
  • Jan Dreier receives a LICS’21 Distinguished Paper Award

    Jan Dreier receives a LICS’21 Distinguished Paper Award

    2021-07-02
    Congratulations to Jan Dreier for his LICS 2021 Distinguished Paper Award for his paper Lacon- and Shrub-Decompositions: A New Characterization …Read More »
  • Lecture at Austrian Parliament

    Lecture at Austrian Parliament

    2021-06-16
    Stefan Szeider and Martin Kronegger gave a lecture on Algorithms and Programming to members of the Austrian Parliament. The lecture …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020 and 2021.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.