### Fast separation in a graph with an excluded minor

*Bruce Reed, David R. Wood*

#### 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 ℓ∈ℤ+ be fixed. Alon, Seymour and Thomas [*J. Amer. Math. Soc.*1990] presented an algorithm that in O(n1/2m) time, either outputs a Kℓ-minor of G, or a separation of G of order O(n1/2). Whether there is a O(n+m) time algorithm for this theorem was left as open problem. In this paper, we obtain a O(n+m) time algorithm at the expense of O(n2/3) separator. Moreover, our algorithm exhibits a tradeoff between running time and the order of the separator. In particular, for any given ε∈[0,1/2], our algorithm either outputs a Kℓ-minor of G, or a separation of G with order O(n(2-ε)/3) in O(n1+ε+m) time.Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page