[hal-01184376] Fast separation in a graph with an excluded minor

Let G be an n-vertex m-edge graph with weighted vertices. A pair of vertex sets A,B⊆V(G) is a \emph2/3-separation of \emphorder |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 [\emphJ. Amer. Math. Soc. 1990] presented an algorithm that in \mathcalO(n^1/2m) time, either outputs a K_ℓ-minor of G, or a separation of G of order \mathcalO(n^1/2). Whether there is a \mathcalO(n+m) time algorithm for this theorem was left as open problem. In this paper, we obtain a \mathcalO(n+m) time algorithm at the expense of \mathcalO(n^2/3) separator. Moreover, our algorithm exhibits a tradeoff between running time and the order of the separator. In particular, for any given \epsilon ∈[0,1/2], our algorithm either outputs a K_ℓ-minor of G, or a separation of G with order \mathcalO(n^(2-\epsilon )/3) in \mathcalO(n^1+\epsilon +m) time.

from HAL : Dernières publications http://ift.tt/1DQQNRX