# Fast separation in a graph with an excluded minor

Abstract : 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{2}{3} - \textit{separation}$ of $\textit{order}$ $|A \cap B|$ if $A \cup B = V(G)$, there is no edge between $A \backslash B$ and $B \backslash A$, and both $A \backslash B$ and $B \backslash A$ have weight at most $\frac{2}{3}$ the total weight of $G$. Let $\ell \in \mathbb{Z}^+$ be fixed. Alon, Seymour and Thomas [$\textit{J. Amer. Math. Soc.}$ 1990] 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,\frac{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.
Keywords :
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.45-50, 2005, DMTCS Proceedings
Domaine :

Littérature citée [9 références]

https://hal.inria.fr/hal-01184376
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 11:38:21
Dernière modification le : jeudi 17 janvier 2019 - 15:58:10
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:03:30

### Fichier

dmAE0110.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184376, version 1

### Citation

Bruce Reed, David R. Wood. Fast separation in a graph with an excluded minor. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.45-50, 2005, DMTCS Proceedings. 〈hal-01184376〉

### Métriques

Consultations de la notice

## 273

Téléchargements de fichiers