Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184376
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:38:21 AM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:03:30 AM

File

dmAE0110.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184376, version 1

Collections

Citation

Bruce Reed, David R. Wood. Fast separation in a graph with an excluded minor. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.45-50. ⟨hal-01184376⟩

Share

Metrics

Record views

310

Files downloads

783