14 citations · 22 across the 11 of their papers we have counts for
6 papers · 1 filter
A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs
Bart M. P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen
We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answ…
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…
Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
Bart M. P. Jansen, Jesper Nederlof
Computing the smallest number such that the vertices of a given graph can be properly -colored is one of the oldest and most fundamental problems in combinatorial optimizati…
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…