Reed, Bruce; Wood, David R. Fast separation in a graph with an excluded minor. (English) Zbl 1192.05082 Felsner, Stefan (ed.), 2005 European conference on combinatorics, graph theory and applications (EuroComb ’05). Extended abstracts from the conference, Technische Universität Berlin, Berlin, Germany, September 5–9, 2005. Paris: Maison de l’Informatique et des Mathématiques Discrètes (MIMD). Discrete Mathematics & Theoretical Computer Science. Proceedings. AE, 45-50, electronic only (2005). Summary: Let \(G\) be an \(n\)-vertex \(m\)-edge graph with weighted vertices. A pair of vertex sets \(A,B\subseteq V(G)\) is a \(\frac 23\)-separation of order \(|A\cap B|\) if \(A\cup B=V(G)\), there is no edge between \(A\diagdown B\) and \(B\diagdown A\), and both \(A\diagdown B\) and \(B\diagdown A\) have weight at most \(\frac 23\) the total weight of \(G\). Let \(\ell \in \mathbb Z^+\) be fixed. N. Alon, P. Seymour and R. Thomas [J. Am. Math. Soc. 3, No. 4, 801–808 (1990; Zbl 0747.05051)] presented an algorithm that in \(\mathcal O(n^{1/2} m)\) time, either outputs a \(K_\ell\)-minor of \(G\), or a separation of \(G\) of order \(\mathcal O(n^{1/2})\). Whether there is a \(\mathcal O(n+m)\) time algorithm for this theorem was left as open problem. In this paper, we obtain a \(\mathcal O (n+m)\) time algorithm at the expense of \(\mathcal O (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 \in [0,1/2]\), our algorithm either outputs a \(K_\ell\) -minor of \(G\), or a separation of \(G\) with order \(\mathcal O (n^{(2-\epsilon)/3})\) in \(\mathcal O(n^{1+\epsilon}+m)\) time.For the entire collection see [Zbl 1088.05001]. Cited in 6 Documents MSC: 05C40 Connectivity 05C83 Graph minors 05C85 Graph algorithms (graph-theoretic aspects) Keywords:graph algorithm; separator; minor Citations:Zbl 0747.05051 PDFBibTeX XMLCite \textit{B. Reed} and \textit{D. R. Wood}, in: 2005 European conference on combinatorics, graph theory and applications (EuroComb '05). Extended abstracts from the conference, Technische Universität Berlin, Berlin, Germany, September 5--9, 2005. Paris: Maison de l'Informatique et des Mathématiques Discrètes (MIMD). 45--50 (2005; Zbl 1192.05082) Full Text: Link