Showing 2018Show all
3 papers · 1 filter
cs.CC2018
Best-case and Worst-case Sparsifiability of Boolean CSPs
Hubie Chen, Bart M. P. Jansen, Astrid Pieterse
We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number…
cs.CC2018
Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations
Bart M. P. Jansen, Astrid Pieterse
We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graph…
cs.CC2018
Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
Bart M. P. Jansen, Astrid Pieterse
The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller…