Safe separators for treewidth |
| |
Authors: | Hans L Bodlaender |
| |
Institution: | a Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, the Netherlands b Zuse Institute Berlin (ZIB), Takustraße 7, D-14195 Berlin, Germany |
| |
Abstract: | A set of vertices S⊆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∪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 inclusion minimal separator of size one or two is safe, every minimum separator of size three that does not split off a component with only one vertex is safe, and every inclusion minimal separator that is an almost clique is safe; an almost clique is a set of vertices W such that there is a v∈W with W-{v} a clique. We report on experiments that show significant reductions of instance sizes for graphs from probabilistic networks and frequency assignment. |
| |
Keywords: | Graph algorithms Treewidth Preprocessing Separators |
本文献已被 ScienceDirect 等数据库收录! |
|