DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Fast separation in a graph with an excluded minor

Bruce Reed, David R. Wood


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

Valid XHTML 1.0 Transitional