4 papers · 1 filter
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 …
Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set
Huib Donkers, Bart M. P. Jansen
The goal of this paper is to open up a new research direction aimed at understanding the power of preprocessing in speeding up algorithms that solve NP-hard problems exactly. We ex…