A linear-time algorithm to find a separator in a graph excluding a minor
Authors:
Open Access
- 1 October 2009
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 5 (4) , 1-16
Abstract
Let G be an n -vertex m -edge graph with weighted vertices. A pair of vertex sets A , B ⊆ V ( G ) is a 2/3 -separation of order | A ∩ B | if A ∪ B = V ( G ), there is no edge between A − B and B − A , and both A − B and B − A have weight at most 2/3 the total weight of G . Let ℓ ∈ Z + be fixed. Alon et al. [1990] presented an algorithm that in O ( n 1/2 m ) time, outputs either a K ℓ -minor of G , or a separation of G of order O ( n 1/2 ). Whether there is a O ( n + m )-time algorithm for this theorem was left as an open problem. In this article, we obtain a O ( n + m )-time algorithm at the expense of a O ( n 2/3 ) separator. Moreover, our algorithm exhibits a trade-off between time complexity and the order of the separator. In particular, for any given ϵ ∈ [0,1/2], our algorithm outputs either a K ℓ -minor of G , or a separation of G with order O ( n (2−ϵ)/3 in O ( n 1 + ϵ + m ) time. As an application we give a fast approximation algorithm for finding an independent set in a graph with no K ℓ-minor.Keywords
This publication has 43 references indexed in Scilit:
- Linearity of grid minors in treewidth with applications through bidimensionalityCombinatorica, 2008
- The Bidimensionality Theory and Its Algorithmic ApplicationsThe Computer Journal, 2007
- Local Tree-Width, Excluded Minors, and Approximation AlgorithmsCombinatorica, 2003
- Partitioning Planar Graphs with Vertex Costs: Algorithms and ApplicationsAlgorithmica, 2000
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination TreeJournal of Algorithms, 1995
- Edge Separators of Planar and Outerplanar Graphs With ApplicationsJournal of Algorithms, 1993
- Improved constants for some separator theoremsJournal of Algorithms, 1987
- Finding small simple cycle separators for 2-connected planar graphsJournal of Computer and System Sciences, 1986
- A separator theorem for graphs of bounded genusJournal of Algorithms, 1984
- Homomorphieeigenschaften und mittlere Kantendichte von GraphenMathematische Annalen, 1967