On brambles, grid-like minors, and parameterized intractability of monadic second-order logic
Stephan Kreutzer, Siamak Tazari · 2009
Brambles were introduced as the dual notion to treewidth, one of the most central concepts of the graph minor theory of Robertson and Seymour. Recently, Grohe and Marx showed that there are graphs G, in which every bramble of order larger than the square root of the treewidth is of exponential size in |G|. On the positive side, they show the existence of polynomial-sized brambles of the order of the square root of the treewidth, up to log factors. We provide the first polynomial time algorithm to construct a bramble in general graphs and achieve this bound, up to log-factors. We use this algorithm to construct grid-like minors, a replacement structure for grid-minors recently introduced by Reed and Wood, in polynomial time. Using the grid-like minors, we introduce the notion of a perfect bramble and an algorithm to find one in polynomial time. Perfect brambles are brambles with a particularly simple structure and they also provide us with a subgraph that has bounded degree and still large treewidth; we use them to obtain a meta-theorem on deciding certain parameterized subgraph-closed problems on general graphs in time singly exponential in the parameter; the only other result with a similar flavor that is known to us is due to Demaine and Hajiaghayi and obtains a doubly-exponential bound on the parameter (albeit, for a more general class of parameterized problems). The second part of our work deals with providing a lower bound to Courcelle’s famous theorem