Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles

Plotkin, Rao, and Smith (SODA’97) showed that any graph with $m$ edges and $n$ vertices that excludes $K_h$ as a depth $O(\mathrm{\ell }\log n)$-minor has a separator of size $O(n\mathrm{/}\mathrm{\ell }+\mathrm{\ell }{h}^2\log n)$ and that such a separator can be found in $O(mn\mathrm{/}\mathrm{\ell })$ time. A time bound of $O(m+n^{2+ϵ}\mathrm{/}\mathrm{\ell })$ for any constant $ϵ>0$ was later given (W., FOCS’11) which is an improvement for non-sparse graphs. We give three new algorithms. The first has the same separator size and running time $O(\mbox{poly}(h)\ell m^{1+\epsilon})$\mathrm{.}Thisisasignificantimprovementforsmall$h$and$\ell$. If $\mathrm{\ell }=\mathrm{\Omega }(n^{{ϵ}^{\mathrm{\prime }}})$ for an arbitrarily small chosen constant ${ϵ}^{\mathrm{\prime }}>0$, we get a time bound of $O(poly(h)\mathrm{\ell }{n}^{1+ϵ})$. The second algorithm achieves the same separator size (with a slightly larger polynomial dependency on $h$) and running time $O(\mbox{poly}(h)(\sqrt\ell n^{1+\epsilon} + n^{2+\epsilon}/\ell^{3/2}))$when$\ell = \Omega(n^{\epsilon’})$\mathrm{.}Ourthirdalgorithmhasrunningtime$O(\mbox{poly}(h)\sqrt\ell n^{1+\epsilon})$when$\ell = \Omega(n^{\epsilon’})$\mathrm{.}Itfindsaseparatorofsize$O(n/\ell) + \tilde O(\mbox{poly}(h)\ell\sqrt n)$whichisnoworsethanpreviousboundswhen$h$isfixedand$\ell = \tilde O(n^{1/4})$. A main tool in obtaining our results is a novel application of a decremental approximate distance oracle of Roditty and Zwick.