AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Min Ones Constraint Satisfaction Problems, i.e., the task of finding a satisfying assignment with at most k true variables (Min Ones SAT(\Gamma)), can express a number of interesting and natural problems. We study the preprocessing properties of this class of problems with respect to k, using the notion of kernelization to capture the viability of preprocessing. We give a dichotomy of Min Ones SAT(\Gamma) problems into admitting or not admitting a kernelization with size guarantee polynomial in k, based on the constraint language \Gamma. We introduce a property of Boolean relations called mergeability that can be easily checked for any \Gamma. When all relations in \Gamma are mergeable, then we show a polynomial kernelization for Min Ones SAT(\Gamma). Otherwise, any \Gamma containing a non-mergeable relation and such that Min Ones SAT(\Gamma) is NP-complete permits us to prove that Min Ones SAT(\Gamma) does not admit a polynomial kernelization unless NP \subseteq co-NP/poly, by a reduction from a particular parameterization of Exact Hitting Set.

This is joint work with Magnus Wahlström.

Stefan Kratsch

--email hidden

passcode not visible

logged in users only