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 $G$ breaks all odd cycles, and thereby yields a bipartite graph…