14 citations · 22 across the 11 of their papers we have counts for
7 papers · 1 filter
Sparsification Lower Bounds for List -Coloring
Hubie Chen, Bart M. P. Jansen, Karolina Okrasa +2
We investigate the List -Coloring problem, the generalization of graph coloring that asks whether an input graph admits a homomorphism to the undirected graph (possibly…
Optimal polynomial-time compression for Boolean Max CSP
Bart M. P. Jansen, Michał Włodarczyk
In the Boolean maximum constraint satisfaction problem - Max CSP - one is given a collection of weighted applications of constraints from a finite constraint language , ove…
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…
Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth
Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon +1
Many combinatorial problems can be solved in time on graphs of treewidth , for a problem-specific constant . In several cases, matching upper and lower bounds…
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…
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…