Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Safe separators for treewidth

Please always quote using this URN: urn:nbn:de:0297-zib-7544
  • A set of vertices $S\subseteq V$ is called a safe separator for treewidth, if $S$ is a separator of $G$, and the treewidth of $G$ equals the maximum of the treewidth over all connected components $W$ of $G-S$ of the graph, obtained by making $S$ a clique in the subgraph of $G$, induced by $W\cup S$. We show that such safe separators are a very powerful tool for preprocessing graphs when we want to compute their treewidth. We give several sufficient conditions for separators to be safe, allowing such separators, if existing, to be found in polynomial time. In particular, every minimal separator of size one or two is safe, every minimal separator of size three that does not split off a component with only one vertex is safe, and every minimal separator that is an almost clique is safe; an almost clique is a set of vertices $W$ such that there is a $v\in W$ with $W-\{v\}$ a clique. We report on experiments that show significant reductions of instance sizes for graphs from proba! bilistic networks and frequency assignment.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Hans L. Bodlaender, Arie M.C.A. Koster
Document Type:ZIB-Report
Tag:preprocessing; safe separators; treewidth
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C85 Graph algorithms [See also 68R10, 68W05]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Rxx Discrete mathematics in relation to computer science / 68R10 Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
Date of first Publication:2003/09/29
Series (Serial Number):ZIB-Report (03-32)
Published in:Appeared in: Discrete Mathematics 306:3 (2006) 337-350. An extended abstract appeared in: Joint Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX '04) and the Workshop on Analytic Algorithmics and Combinatorics (ANALCO '04), New Oreleans, SIAM Proceedings, pp. 70-78 (2004)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.