Weighted Excluded-Minor Separator Theorem

Claim/Theorem

Alon, Seymour, and Thomas prove a weighted separator theorem for excluded-minor graphs. Let \(H\) be a simple graph with \(h\) vertices, let \(G\) be an \(n\)-vertex graph with no \(H\)-minor, and let \(w:V(G)\to \mathbb{R}_{\ge 0}\) be any nonnegative vertex-weight function. Then there exists a separation \((A,B)\) of \(G\) with

\[ |A\cap B|\;\le\;h^{3/2}\sqrt{n}, \]

and

\[ w(A\setminus B),\;w(B\setminus A)\;\le\;\frac{2}{3}\,w(V(G)). \]

Consequently, every fixed-minor-free graph family admits balanced weighted separators of size \(O_H(\sqrt{r})\) on every \(r\)-vertex subgraph. Planar graphs are a special case because they exclude \(K_5\) and \(K_{3,3}\) minors.

Dependencies

• None.

Conflicts/Gaps

• This is a vertex-separator theorem, not yet an edge-boundary theorem. To use it in a circuit lower bound one must translate separator size into hardware cut capacity, typically via bounded hardware degree.
• The constant depends on the excluded minor \(H\). The theorem is strongest when \(H\) is fixed across the hardware family.
• The theorem controls the total weight outside the separator, not the weight placed on the separator itself. When only data qubits are weighted, one must still account for the possibility that the separator contains \(O_H(\sqrt{r})\) data qubits.

Sources

• 10.1145/100216.100254