×

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].

MSC:

05C40 Connectivity
05C83 Graph minors
05C85 Graph algorithms (graph-theoretic aspects)

Citations:

Zbl 0747.05051
PDFBibTeX XMLCite
Full Text: Link