Sparsification of SAT and CSP Problems via Tractable Extensions

DOI10.1145/3389411zbMath1499.68241OpenAlexW3023177507MaRDI QIDQ5053064

Magnus Wahlström, Victor Lagerkvist

Publication date: 5 December 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3389411

zbMATH Keywords

constraint satisfaction problemsuniversal algebrasatisfiability problemssparsificationkernelization

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Related Items (4)

Unnamed Item ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ General lower bounds and improved algorithms for infinite-domain CSPs ⋮ Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms

This page was built for publication: Sparsification of SAT and CSP Problems via Tractable Extensions