Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with\n Applications

Alon, Seymour, and Thomas generalized Lipton and Tarjan's planar separator\ntheorem and showed that a $K_h$-minor free graph with $n$ vertices has a\nseparator of size at most $h^{3/2}\\sqrt n$. They gave an algorithm that, given\na graph $G$ with $m$ edges and $n$ vertices and given an integer $h\\geq 1$,\noutputs in $O(\\sqrt{hn}m)$ time such a separator or a $K_h$-minor of $G$.\nPlotkin, Rao, and Smith gave an $O(hm\\sqrt{n\\log n})$ time algorithm to find a\nseparator of size $O(h\\sqrt{n\\log n})$. Kawarabayashi and Reed improved the\nbound on the size of the separator to $h\\sqrt n$ and gave an algorithm that\nfinds such a separator in $O(n^{1 + \\epsilon})$ time for any constant $\\epsilon\n> 0$, assuming $h$ is constant. This algorithm has an extremely large\ndependency on $h$ in the running time (some power tower of $h$ whose height is\nitself a function of $h$), making it impractical even for small $h$. We are\ninterested in a small polynomial time dependency on $h$ and we show how to find\nan $O(h\\sqrt{n\\log n})$-size separator or report that $G$ has a $K_h$-minor in\n$O(\\poly(h)n^{5/4 + \\epsilon})$ time for any constant $\\epsilon > 0$. We also\npresent the first $O(\\poly(h)n)$ time algorithm to find a separator of size\n$O(n^c)$ for a constant $c < 1$. As corollaries of our results, we get improved\nalgorithms for shortest paths and maximum matching. Furthermore, for integers\n$\\ell$ and $h$, we give an $O(m + n^{2 + \\epsilon}/\\ell)$ time algorithm that\neither produces a $K_h$-minor of depth $O(\\ell\\log n)$ or a separator of size\nat most $O(n/\\ell + \\ell h^2\\log n)$. This improves the shallow minor algorithm\nof Plotkin, Rao, and Smith when $m = \\Omega(n^{1 + \\epsilon})$. We get a\nsimilar running time improvement for an approximation algorithm for the problem\nof finding a largest $K_h$-minor in a given graph.\n

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.