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-parameter tractability of constrained separation and bipartization problems. To demonstrate the power of this technique, we prove the fixed-parameter tractability of a number of well-known separation and bipartization problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set). These...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our Documentation.