SAT Based Local Improvement (Research Project)

Funding organization: Austrian Science Fund (FWF)

Project number: (FWF P 32441)

Project Team

Stefan Szeider (PI)

André Schidler

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

6 results
2020
[6]A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth
,
Proceedings of SAT 2020, The 23rd International Conference on Theory and Applications of Satisfiability Testing (Luca Pulina, Martina Seidl, eds.), 2020, Springer Verlag.
Note: to appear
[bibtex] [pdf]
[5]Short Q-Resolution Proofs with Homomorphisms
, ,
Proceedings of SAT 2020, The 23rd International Conference on Theory and Applications of Satisfiability Testing (Luca Pulina, Martina Seidl, eds.), 2020, Springer Verlag.
Note: to appear
[bibtex] [pdf]
[4]Computing Optimal Hypertree Decompositions
,
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]
[3]Threshold Treewidth and Hypertree Width
, , ,
Proceeding of IJCAI-PRICAI2020, the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence, 2020.
Note: to appear
[bibtex] [pdf]
[2]Fixed-Parameter Tractability of Dependency QBF with Structural Parameters
, , ,
Principles of Knowledge Representation and Reasoning: Proceedings of the Seventeenth International Conference, KR 2020, 2020.
Note: to appear
[bibtex]
[1]On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Dimension
, , ,
The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 3906–3913, 2020, AAAI Press.
[bibtex] [pdf]