Treewidth reduction for constrained separation and bipartization problems

Dániel Marx, Barry O'Sullivan, Igor Razgon

We present a method for reducing the treewidth of a graph while preserving all the minimal $s-t$ separators. This technique turns out to be very useful for establishing the fixed-p…