Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

Description

It is shown that for each $t$, there is a separator of size $O(t sqrt{n})$ in any $n$-vertex graph $G$ with no $K_t$-minor.

This settles a conjecture of Alon, Seymour and Thomas (J. Amer. Math. Soc., 1990 and STOC'90), and generalizes a result of Djidjev (1981), and Gilbert, Hutchinson and Tarjan (J. Algorithm, 1984), independently, who proved that every graph with $n$ vertices and genus $g$ has a separator of order $O(sqrt{gn})$, because $K_t$ has genus $Omega(t^2)$.

The bound $O(t sqrt{n})$ is best possible because every 3-regular expander graph with $n$ vertices is a graph with no $K_t$-minor for $t=cn^{1/2}$, and with no separator of size $dn$ for appropriately chosen positive constants $c,d$.

In addition, we give an $O(n^2)$ time algorithm to obtain such a separator, and then give a sketch how to obtain such a separator in $O(n^{1+epsilon})$ time for any $epsilon > 0$. Finally, we discuss several algorithm aspects of our separator theorem, including a possibility to obtain a separator of order $g(t)sqrt{n}$, for some function $g$ of $t$, in an $n$-vertex graph $G$ with no $K_t$-minor in $O(n)$ time.

Questions and Answers

You need to be logged in to be able to post here.