A Linear-Time Algorithm to Find a Separator in a Graph Excluding a Minor

Abstract

<jats:p> Let <jats:italic>G</jats:italic> be an <jats:italic>n</jats:italic> -vertex <jats:italic>m</jats:italic> -edge graph with weighted vertices. A pair of vertex sets <jats:italic>A</jats:italic> , <jats:italic>B</jats:italic> ⊆ <jats:italic>V</jats:italic> ( <jats:italic>G</jats:italic> ) is a 2/3 <jats:italic>-separation</jats:italic> of <jats:italic>order</jats:italic> | <jats:italic>A</jats:italic> ∩ <jats:italic>B</jats:italic> | if <jats:italic>A</jats:italic> ∪ <jats:italic>B</jats:italic> = <jats:italic>V</jats:italic> ( <jats:italic>G</jats:italic> ), there is no edge between <jats:italic>A</jats:italic> − <jats:italic>B</jats:italic> and <jats:italic>B</jats:italic> − <jats:italic>A</jats:italic> , and both <jats:italic>A</jats:italic> − <jats:italic>B</jats:italic> and <jats:italic>B</jats:italic> − <jats:italic>A</jats:italic> have weight at most 2/3 the total weight of <jats:italic>G</jats:italic> . Let ℓ ∈ Z <jats:sup>+</jats:sup> be fixed. Alon et al. [1990] presented an algorithm that in <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> <jats:sup>1/2</jats:sup> <jats:italic>m</jats:italic> ) time, outputs either a <jats:italic>K</jats:italic> <jats:sub>ℓ</jats:sub> -minor of <jats:italic>G</jats:italic> , or a separation of <jats:italic>G</jats:italic> of order <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> <jats:sup>1/2</jats:sup> ). Whether there is a <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> + <jats:italic>m</jats:italic> )-time algorithm for this theorem was left as an open problem. In this article, we obtain a <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> + <jats:italic>m</jats:italic> )-time algorithm at the expense of a <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> <jats:sup>2/3</jats:sup> ) 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 <jats:italic>K</jats:italic> <jats:sub>ℓ</jats:sub> -minor of <jats:italic>G</jats:italic> , or a separation of <jats:italic>G</jats:italic> with order <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> <jats:sup>(2−ϵ)/3</jats:sup> in <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> <jats:sup>1 + ϵ</jats:sup> + <jats:italic>m</jats:italic> ) time. As an application we give a fast approximation algorithm for finding an independent set in a graph with no <jats:italic>K</jats:italic> ℓ-minor. </jats:p>