2026-07-20T05:31:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2485 2024-03-06T10:33:26Z ddc:004 open_access

Treewidth Reduction for Constrained Separation and Bipartization Problems Marx, Dániel O'Sullivan, Barry Razgon, Igor Fixed-parameter algorithms graph separation problems treewidth 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dániel Marx and Barry O'Sullivan and Igor Razgon 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2485 urn:nbn:de:0030-drops-24850 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2485 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode