Best-case and worst-case sparsifiability of Boolean CSPs
DOI10.1007/s00453-019-00660-yzbMath1452.68176OpenAlexW3000512743MaRDI QIDQ786033
Bart M. P. Jansen, Hubie Chen, Astrid Pieterse
Publication date: 12 August 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10216/
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)
Related Items (5)
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Kernel bounds for disjoint cycles and disjoint paths
- On sparsification for computing treewidth
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Weak bases of Boolean co-clones
- Kernelization – Preprocessing with a Guarantee
- The power of primitive positive definitions with polynomially many variables
- New Limits to Classical and Quantum Instance Compression
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
- Point Line Cover
- Kernelization Lower Bounds by Cross-Composition
- Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
- Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
This page was built for publication: Best-case and worst-case sparsifiability of Boolean CSPs
