On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic

Details On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic

2009-07-17

arxiv.org/abs/0907.3076v1

Computer Science

Discrete Mathematics

Scientific paper

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 second part of our work deals with providing a lower bound to Courcelle's famous theorem, stating that every graph property that can be expressed by a sentence in monadic second-order logic (MSO), can be decided by a linear time algorithm on classes of graphs of bounded treewidth. Using our results from the first part of our work we establish a strong lower bound for tractability of MSO on classes of colored graphs.

Affiliated with

Also associated with

No associations

Rating

On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-110811