TY - GEN
T1 - Treewidth reduction for constrained separation and bipartization problems
AU - Marx, Dániel
AU - O'Sullivan, Barry
AU - Razgon, Igor
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - Fixed-parameter algorithms
KW - Graph separation problems
KW - Treewidth
UR - https://www.scopus.com/pages/publications/84880311521
U2 - 10.4230/LIPIcs.STACS.2010.2458
DO - 10.4230/LIPIcs.STACS.2010.2458
M3 - Conference proceeding
AN - SCOPUS:84880311521
SN - 9783939897163
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 561
EP - 572
BT - STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science
T2 - 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010
Y2 - 4 March 2010 through 6 March 2010
ER -