Best-case and worst-case sparsifiability of Boolean CSPs
type: Item
instance of: scholarly article
title: Best-case and worst-case sparsifiability of Boolean CSPs
zbMATH Open document ID: 1452.68176
author: Hubie Chen
author: Bart M. P. Jansen
author: Astrid Pieterse
published in: Algorithmica
publication date: 2020-08-12T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10216/
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68R07
zbMATH DE Number: 7233374
zbMATH Keywords: constraint satisfaction problems
zbMATH Keywords: kernelization
zbMATH Keywords: sparsification
zbMATH Keywords: lower bounds
MaRDI profile type: Publication
OpenAlex ID: W3000512743
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: Kernel bounds for disjoint cycles and disjoint paths
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: Parameterized Algorithms
cites work: Q5743378
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Fundamentals of parameterized complexity
cites work: New Limits to Classical and Quantum Instance Compression
cites work: On sparsification for computing treewidth
cites work: Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
cites work: Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
cites work: Sparsification upper and lower bounds for graph problems and not-all-equal SAT
cites work: Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
cites work: Point Line Cover
cites work: Weak bases of Boolean co-clones
cites work: The power of primitive positive definitions with polynomially many variables
cites work: Kernelization – Preprocessing with a Guarantee
cites work: Q3859790
cites work: The complexity of satisfiability problems
DOI: 10.1007/S00453-019-00660-Y
description: scientific article; zbMATH DE number 7233374