LIPIcs.STACS.2010.2485.pdf
- Filesize: 126 kB
- 12 pages
Document
Treewidth Reduction for Constrained Separation and Bipartization Problems
Authors
-
Part of:
Volume:
27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2010-03-09
Cite AsGet BibTex
Dániel Marx, Barry O'Sullivan, and Igor Razgon. Treewidth Reduction for Constrained Separation and Bipartization Problems. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 561-572, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/LIPIcs.STACS.2010.2485
https://doi.org/10.4230/LIPIcs.STACS.2010.2485
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.
Keywords
- Fixed-parameter algorithms
- graph separation problems
- treewidth
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads