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

16 results

2021
[16]	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]
[15]	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]
[14]	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]
[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]
[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 Workshop 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]