Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials

DOI10.1145/3349618zbMath1495.68100MaRDI QIDQ5205824

Bart M. P. Jansen, Astrid Pieterse

Publication date: 16 December 2019

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6482/

zbMATH Keywords

satisfiability; constraint satisfaction problem; sparsification; kernelization

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C27: Combinatorial optimization

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q27: Parameterized complexity, tractability and kernelization

68R07: Computational aspects of satisfiability