On the Parameterized Intractability of Monadic Second-Order Logic
One of Courcelle's celebrated results states that if C is a class of graphs of bounded tree-width, then model-checking for monadic second order logic (MSO_2) is fixed-parameter tractable (fpt) on C by linear time parameterized algorithms, where the parameter is the tree-width plus the size of t...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2012-03-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/785/pdf |
| _version_ | 1797268709317804032 |
|---|---|
| author | Stephan Kreutzer |
| author_facet | Stephan Kreutzer |
| author_sort | Stephan Kreutzer |
| collection | DOAJ |
| description | One of Courcelle's celebrated results states that if C is a class of graphs
of bounded tree-width, then model-checking for monadic second order logic
(MSO_2) is fixed-parameter tractable (fpt) on C by linear time parameterized
algorithms, where the parameter is the tree-width plus the size of the formula.
An immediate question is whether this is best possible or whether the result
can be extended to classes of unbounded tree-width. In this paper we show that
in terms of tree-width, the theorem cannot be extended much further. More
specifically, we show that if C is a class of graphs which is closed under
colourings and satisfies certain constructibility conditions and is such that
the tree-width of C is not bounded by \log^{84} n then MSO_2-model checking is
not fpt unless SAT can be solved in sub-exponential time. If the tree-width of
C is not poly-logarithmically bounded, then MSO_2-model checking is not fpt
unless all problems in the polynomial-time hierarchy can be solved in
sub-exponential time. |
| first_indexed | 2024-04-25T01:36:47Z |
| format | Article |
| id | doaj.art-9bf3a047acd1443c96043b790e3fed66 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:36:47Z |
| publishDate | 2012-03-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-9bf3a047acd1443c96043b790e3fed662024-03-08T09:27:54ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742012-03-01Volume 8, Issue 110.2168/LMCS-8(1:27)2012785On the Parameterized Intractability of Monadic Second-Order LogicStephan KreutzerOne of Courcelle's celebrated results states that if C is a class of graphs of bounded tree-width, then model-checking for monadic second order logic (MSO_2) is fixed-parameter tractable (fpt) on C by linear time parameterized algorithms, where the parameter is the tree-width plus the size of the formula. An immediate question is whether this is best possible or whether the result can be extended to classes of unbounded tree-width. In this paper we show that in terms of tree-width, the theorem cannot be extended much further. More specifically, we show that if C is a class of graphs which is closed under colourings and satisfies certain constructibility conditions and is such that the tree-width of C is not bounded by \log^{84} n then MSO_2-model checking is not fpt unless SAT can be solved in sub-exponential time. If the tree-width of C is not poly-logarithmically bounded, then MSO_2-model checking is not fpt unless all problems in the polynomial-time hierarchy can be solved in sub-exponential time.https://lmcs.episciences.org/785/pdfcomputer science - logic in computer sciencef.4.1 |
| spellingShingle | Stephan Kreutzer On the Parameterized Intractability of Monadic Second-Order Logic Logical Methods in Computer Science computer science - logic in computer science f.4.1 |
| title | On the Parameterized Intractability of Monadic Second-Order Logic |
| title_full | On the Parameterized Intractability of Monadic Second-Order Logic |
| title_fullStr | On the Parameterized Intractability of Monadic Second-Order Logic |
| title_full_unstemmed | On the Parameterized Intractability of Monadic Second-Order Logic |
| title_short | On the Parameterized Intractability of Monadic Second-Order Logic |
| title_sort | on the parameterized intractability of monadic second order logic |
| topic | computer science - logic in computer science f.4.1 |
| url | https://lmcs.episciences.org/785/pdf |
| work_keys_str_mv | AT stephankreutzer ontheparameterizedintractabilityofmonadicsecondorderlogic |