Improved Bounds for the Flat Wall Theorem

The Flat Wall Theorem of Robertson and Seymour states that there is some function f, such that for all integers w,t>1, every graph G containing a wall of size f(w,t), must contain either (i) a Kt-minor; or (ii) a small subset Asubset V(G) of vertices, and a flat wall of size w in Gsetminus A. Kawarabayashi, Thomas and Wollan recently showed a self-contained proof of this theorem with the following two sets of parameters: (1) f(w,t)=Theta(t24(t2+w)) with |A|=O(t24), and (2) f(w,t)=w^2^Theta(t24) with |A|≤ t-5. The latter result gives the best possible bound on |A|. In this paper we improve their bounds to f(w,t)=Theta(t(t+w)) with |A|≤ t-5. For the special case where the maximum vertex degree in G is bounded by D, we show that, if G contains a wall of size Omega(Dt(t+w)), then either G contains a Kt-minor, or there is a flat wall of size w in G. This setting naturally arises in algorithms for the Edge-Disjoint Paths problem, with D≤ 4. Like the proof of Kawarabayashi et al., our proof is self-contained, except for using a well-known theorem on routing pairs of disjoint paths. We also provide efficient algorithms that return either a model of the Kt-minor, or a vertex set A and a flat wall of size w in Gsetminus A. We complement our result for the low-degree scenario by proving an almost matching lower bound: namely, for all integers w,t>1, there is a graph G, containing a wall of size Omega(wt), such that the maximum vertex degree in G is 5, and G contains no flat wall of size w, and no Kt-minor.