Sparsification of Constraint Satisfaction Problems with an application to q-Coloring
- Speaker: Astrid Pieterse, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven
- Date: Tuesday, 20 February 2018 from 17:00 to 18:00
- Location: Room 151
Abstract: In this talk we study the sparsification of NP-hard constraint satisfaction problems (CSPs). Given an input instance, the aim is to efficiently reduce the number of constraints without changing the answer. We investigate deterministic polynomial-time sparsification in a worst-case setting. For any fixed constraint language Gamma, the goal is to find the smallest constant c for which any n-variable instance of CSP(Gamma) can be efficiently reduced to an equivalent instance with O(n^c) constraints. We would like to find out how the constraint language influences the sparsifiability of the problem (the optimal value of c).
Towards this goal, we characterize constraint types based on the minimum degree of multivariate polynomials whose roots correspond to the satisfying assignments, obtaining (nearly) matching upper and lower bounds in several settings.
Furthermore, we show how to use this result to obtain a kernel for the Graph q-Coloring problem. Here, we show how to efficiently reduce a q-Coloring input to an equivalent but smaller input, whose size is bounded in terms of structural properties of the original graph, such as the size of a minimum vertex cover.
Based on papers at MFCS 2016 and IPEC 2017; joint work with Bart M. P. Jansen.