4 papers
Search-space Reduction for Boolean MinCSPs via Essential Constraints
Bart M. P. Jansen, Ruben F. A. Verhaegh
For a fixed set of Boolean constraint types, a MinCSP-instance consists of a formula that applies constraints from to a set of $n…
An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange
Bart M. P. Jansen, Jeroen S. K. Lamme, Ruben F. A. Verhaegh
We study the parameterized complexity of a recently introduced multi-agent variant of the Kidney Exchange problem. Given a directed graph and integers and , the standard…
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…
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 .…