Improved bounds for the flat wall theorem

DOI10.1137/1.9781611973730.20MaRDI QIDQ5363032zbMATH OpenOpenAlexFDO

Authors Julia Chuzhoy

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.0276

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 $K_t$-minor; or (ii) a small subset $AsubsetV(G)$ of vertices, and a flat wall of size $w$ in $GsetminusA$. 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(t^{24}(t^2+w))$ with $|A|=O(t^{24})$, and (2) $f(w,t)=w^{2^{Theta(t^{24})}}$ with $|A|leqt-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|leqt-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 $K_t$-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 $Dleq4$. 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 $K_t$-minor, or a vertex set $A$ and a flat wall of size $w$ in $GsetminusA$. 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 $K_t$-minor.

Recommendations

• A new proof of the flat wall theorem
• Optimizing the graph minors weak structure theorem
• Polynomial bounds for the grid-minor theorem
• Tree-width and planar minors
• Polynomial bounds for the grid-minor theorem

Cited in

(16)

• Logarithmic lower bounds for Néel walls
• Colouring square-free graphs without long induced paths
• Steiner trees for hereditary graph classes: a treewidth perspective
• Optimizing the graph minors weak structure theorem
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• scientific article; zbMATH DE number 7204407 (Why is no real title available?)
• Clique-width for graph classes closed under complementation
• Block elimination distance
• k-apices of minor-closed graph classes. I: Bounding the obstructions
• Packing cycles in undirected group-labelled graphs
• Clique‐width: Harnessing the power of atoms
• A more accurate view of the flat wall theorem
• A new proof of the flat wall theorem
• On the size of two minimal linkages
• Compound logics for modification problems

This page was built for publication: Improved bounds for the flat wall theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363032)