Treewidth reduction for constrained separation and bipartization problems

Abstract : 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.
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/inria-00455767
Contributor : Publications Loria <>
Submitted on : Thursday, February 11, 2010 - 10:33:03 AM
Last modification on : Saturday, October 14, 2017 - 1:03:59 AM
Long-term archiving on : Friday, June 18, 2010 - 8:11:05 PM

File

Marx.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455767, version 1

Collections

Citation

Dániel Marx, Barry O'Sullivan, Igor Razgon. Treewidth reduction for constrained separation and bipartization problems. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.561-572. ⟨inria-00455767⟩

Share

Metrics

Record views

150

Files downloads

137