Marx, Dániel
[VerfasserIn];
O'Sullivan, Barry
[VerfasserIn];
Razgon, Igor
[VerfasserIn]
;
Dániel Marx and Barry O'Sullivan and Igor Razgon
[MitwirkendeR]
Treewidth Reduction for Constrained Separation and Bipartization Problems
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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 results answer a number of open questions in the area of parameterized complexity.