Sparsification of SAT and CSP Problems via Tractable Extensions

DOI10.1145/3389411MaRDI QIDQ5053064zbMATH OpenOpenAlexFDO

Authors Victor Lagerkvist, Magnus Wahlström

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 problemskernelizationsatisfiability problemssparsificationuniversal algebra

Mathematics Subject Classification ID

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

Recommendations

• Sparsification of Binary CSPs
• Sparsification of binary CSPs
• Additive Sparsification of CSPs.
• Approximating satisfiable satisfiability problems (extended abstract)
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT
• The algebraic structure of the densification and the sparsification tasks for CSPs
• Sparsification upper and lower bounds for graphs problems and not-all-equal SAT
• On the efficient approximability of constraint satisfaction problems
• Improved algorithms for sparse MAX-SAT and MAX-k-CSP
• Structural tractability of enumerating CSP solutions

Cited in

(16)

• Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT
• General lower bounds and improved algorithms for infinite-domain CSPs
• On the limits of sparsification
• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
• SAT-solving in CSP trace refinement
• Optimal sparsification for some binary CSPs using low-degree polynomials
• Best-case and worst-case sparsifiability of Boolean CSPs
• Optimal sparsification for some binary CSPs using low-degree polynomials
• Sparsification upper and lower bounds for graphs problems and not-all-equal SAT
• A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms
• The algebraic structure of the densification and the sparsification tasks for CSPs
• Algebraic global gadgetry for surjective constraint satisfaction
• Optimal polynomial-time compression for Boolean Max CSP
• Best-case and worst-case sparsifiability of Boolean CSPs
• Solving sparse instances of Max SAT via width reduction and greedy restriction

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

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