Computing optimal hypertree decompositions with SAT

DOI10.1016/J.ARTINT.2023.104015MaRDI QIDQ6067037zbMATH OpenOpenAlexFDO

Authors André Schidler, Stefan Szeider

Publication date 14 December 2023

Published in Artificial Intelligence (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.artint.2023.104015

zbMATH Keywords

constraint programminghypertree widthMaxSAToptimizationSATSAT encodingSMT

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Programming involving graphs or networks (90C35)

Recommendations

• A backtracking-based algorithm for hypertree decomposition
• Graph-Theoretic Concepts in Computer Science
• Threshold Treewidth and Hypertree Width
• Fast parallel hypertree decompositions in logarithmic recursion depth
• Computing hypergraph width measures exactly

Cites work

• \textsc{OptiMathSAT}: a tool for optimization modulo theories
• A backtracking-based algorithm for hypertree decomposition
• A survey of satisfiability modulo theory
• Abstract cores in implicit hitting set MaxSat solving
• Computing Optimal Hypertree Decompositions
• Efficient CNF encoding of Boolean cardinality constraints
• Encoding Treewidth into SAT
• Fast and parallel decomposition of constraint satisfaction problems
• Fundamentals of parameterized complexity
• Graph-Theoretic Concepts in Computer Science
• HyperBench. A benchmark and tool for hypergraphs and empirical findings
• Hypertree decompositions and tractable queries
• Jdrasil: a modular library for computing tree decompositions
• MiniCon: a scalable algorithm for answering queries using views
• PySAT: a Python toolkit for prototyping with SAT oracles
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• SAT-encodings for special treewidth and pathwidth
• SAT-encodings for treecut width and treedepth
• SOFSEM 2005: Theory and Practice of Computer Science
• Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
• The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints

Cited in

(5)

• Finding optimal satisficing strategies for and-or trees
• Decomposing SAT Instances with Pseudo Backbones
• Fast parallel hypertree decompositions in logarithmic recursion depth
• Minimum partition into plane subgraphs: the CG:SHOP challenge 2022
• Computing and certifying twin-width using logic

This page was built for publication: Computing optimal hypertree decompositions with SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6067037)