2014/10/01 by Chuzhoy, Julia · 1 citation
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1410.0276
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 A⊂ V(G) of vertices, and a flat wall of size w in G∖ 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)=Θ(t24(t2+w)) with |A|=O(t24), and (2) f(w,t)=w^2^Θ(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)=Θ(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 Ω(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 G∖ 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 Ω(wt), such that the maximum vertex degree in G is 5, and G contains no flat wall of size w, and no Kt-minor.