A Separator for Minor-Free Graphs Beyond the Flow Barrier

In 1990, Alon, Seymour, and Thomas gave the first balanced separator of size $O(h^{3/2}\sqrt{n})$ for any $K_h$-minor-free graph, which has had numerous algorithmic applications. They conjectured that the size of the balanced separator can be reduced to $O(h\sqrt{n})$, which is asymptotically tight. Two decades later, Kawarabayashi and Reed constructed a separator of size $O(h\sqrt{n} + f(h))$ based on the graph minor structure theorem, where $f(h)$ is an extremely fast-growing function; their separator's size is only better for a very small value of $h$. Recently, Spalding-Jamieson constructed a separator of size $O(h\log h \log\log h \sqrt{n})$; the technique is rooted in concurrent flow-sparsest cut duality. Spalding-Jamieson's separator comes very close to $O(h\log h \sqrt{n})$, which is the barrier for techniques based on the flow-cut duality. In this work, we first present a simple adaptation of a flow-based algorithm of Korhonen and Lokshtanov to construct a balanced separator of size $O(h\log h \sqrt{n})$, matching the flow barrier. This result motivates the question of whether the flow barrier can be broken, which would be a stepping stone toward resolving the conjecture of Alon, Seymour, and Thomas. The main result of our work is a positive answer to this question: we construct a balanced separator of size $O(h \sqrt{\log h} \sqrt{n})$. Surprisingly, perhaps, our algorithm is still based on the iterative framework of Alon, Seymour, and Thomas, although a key component of their algorithm within this framework, called the neighborhood bound, was shown to be tight. Our new idea is to incorporate a low-diameter decomposition into the framework, allowing us to reduce the neighborhood bound by a factor of $h$, at the cost of a factor $\log h$, which translates to a reduction from $\sqrt{h}$ to $\sqrt{\log h}$ in the final separator's size.