Chen, Hubie ;
Jansen, Bart M. P. ;
Pieterse, Astrid
BestCase and WorstCase Sparsifiability of Boolean CSPs
Abstract
We continue the investigation of polynomialtime sparsification for NPcomplete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance without changing the answer, such that a bound on the number of resulting constraints can be given in terms of the number of variables n. We investigate how the worstcase sparsification size depends on the types of constraints allowed in the problem formulation (the constraint language). Two algorithmic results are presented. The first result essentially shows that for any arity k, the only constraint type for which no nontrivial sparsification is possible has exactly one falsifying assignment, and corresponds to logical OR (up to negations). Our second result concerns linear sparsification, that is, a reduction to an equivalent instance with O(n) constraints. Using linear algebra over rings of integers modulo prime powers, we give an elegant necessary and sufficient condition for a constraint type to be captured by a degree1 polynomial over such a ring, which yields linear sparsifications. The combination of these algorithmic results allows us to prove two characterizations that capture the optimal sparsification sizes for a range of Boolean CSPs. For NPcomplete Boolean CSPs whose constraints are symmetric (the satisfaction depends only on the number of 1 values in the assignment, not on their positions), we give a complete characterization of which constraint languages allow for a linear sparsification. For Boolean CSPs in which every constraint has arity at most three, we characterize the optimal size of sparsifications in terms of the largest OR that can be expressed by the constraint language.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2019:10216,
author = {Hubie Chen and Bart M. P. Jansen and Astrid Pieterse},
title = {{BestCase and WorstCase Sparsifiability of Boolean CSPs}},
booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
pages = {15:115:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770842},
ISSN = {18688969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10216},
URN = {urn:nbn:de:0030drops102169},
doi = {10.4230/LIPIcs.IPEC.2018.15},
annote = {Keywords: constraint satisfaction problems, kernelization, sparsification, lower bounds}
}
05.02.2019
Keywords: 

constraint satisfaction problems, kernelization, sparsification, lower bounds 
Seminar: 

13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Issue date: 

2019 
Date of publication: 

05.02.2019 