Lower Bounds on the Complexity of MSO1 Model-Checking

Details Lower Bounds on the Complexity of MSO1 Model-Checking Lower Bounds on the Complexity of MSO1 Model-Checking

2011-09-27

arxiv.org/abs/1109.5804v1

Computer Science

Discrete Mathematics

Scientific paper

One of the most important algorithmic meta-theorems is a famous result by Courcelle which states that any graph problem definable in monadic second-order logic with edge-set quantification (MSO2) is decidable in linear time on any class of graphs of bounded tree-width. In the parlance of parameterized complexity, this means that MSO2 is FPT-tractable wrt. the tree-width as parameter. Recently, Kreutzer and Tazari have given a sort of corresponding complexity lower-bound - that MSO2 model-checking is not even XP-tractable (modulo a certain complexity-theoretical assumption, namely the ETH)for graph classes that are subgraph-closed, and whose tree-width is poly-logarithmically unbounded. We present a closely related result, showing that even MSO1 model-checking with a fixed set of vertex labels, but without edge-set quantification, is not XP-tractable for graph classes which are subgraph-closed and whose tree-width is poly-logarithmically unbounded (unless the nonuniform ETH fails). In comparison to Kreutzer and Tazari; (I) we completely avoid an, in our opinion unnatural, effectiveness assumption in their results, (II) assume a much smaller set of problems to be efficiently solvable in our arguments---those definable in MSO1-L instead of MSO2, and (III) give short and streamlined proofs. Furthermore, our result has an interesting consequence in the realm of digraph width measures: Strengthening the recent result of Ganian et al., we get that no subdigraph-monotone measure can be algorithmically useful, unless it is within a poly-logarithmic factor of the ordinary (undirected) tree-width.

Affiliated with

Also associated with

No associations

Rating

Lower Bounds on the Complexity of MSO1 Model-Checking 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 Lower Bounds on the Complexity of MSO1 Model-Checking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bounds on the Complexity of MSO1 Model-Checking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-62203