114 citations · 385 across the 36 of their papers we have counts for
54 papers
Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2
We say that an instance of a constraint satisfaction problem (CSP) is non-redundant if the satisfaction of each clause cannot be implied by the satisfaction of the other clauses in…
Preprocessing to Reduce the Search Space for Odd Cycle Transversal
Bart M. P. Jansen, Yosuke Mizutani, Blair D. Sullivan +1
The NP-hard Odd Cycle Transversal problem asks for a minimum vertex set whose removal from an undirected input graph breaks all odd cycles, and thereby yields a bipartite graph…
Steiner Tree Parameterized by Multiway Cut and Even Less
Bart M. P. Jansen, Céline M. F. Swennenhuis
In the Steiner Tree problem we are given an undirected edge-weighted graph as input, along with a set of vertices called terminals. The task is to output a minimum-weight conne…
Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion
Bart M. P. Jansen, Ruben F. A. Verhaegh
For an optimization problem on graphs whose solutions are vertex sets, a vertex is called -essential for if all solutions of size at most contain .…
On the Parameterized Complexity of Multiway Near-Separator
Bart M. P. Jansen, Shivesh K. Roy
We study a new graph separation problem called Multiway Near-Separator. Given an undirected graph , integer , and terminal set , it asks whether there is a…
Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions
Bart M. P. Jansen, Bart van der Steenhoven
A kernelization for a parameterized decision problem is a polynomial-time preprocessing algorithm that reduces any parameterized instance into an instance $(x…