Lower Bounds on the Complexity of MSO_1 Model-Checking
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F12%3A00057595" target="_blank" >RIV/00216224:14330/12:00057595 - isvavai.cz</a>
Result on the web
<a href="http://stacs2012.lip6.fr/" target="_blank" >http://stacs2012.lip6.fr/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2012.326" target="_blank" >10.4230/LIPIcs.STACS.2012.326</a>
Alternative languages
Result language
angličtina
Original language name
Lower Bounds on the Complexity of MSO_1 Model-Checking
Original language description
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 quantifications (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 model-checking is fixed-parameter tractable with respect to the tree-width as parameter. Recently, Kreutzer and Tazari proved a corresponding complexity lower-bound---that MSO2 model-checking is not even in XP wrt the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. Of course, this is not an unconditional result but holds modulo a certain complexity-theoretic assumption, namely, the Exponential Time Hypothesis (ETH). In this paper we present a closely related result.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GAP202%2F11%2F0196" target="_blank" >GAP202/11/0196: Well-structured combinatorial classes, width parameters, and design of efficient algorithms</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
29th International Symposium on Theoretical Aspects of Computer Science STACS2012
ISBN
9783939897354
ISSN
1868-8969
e-ISSN
—
Number of pages
12
Pages from-to
326-337
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS
Place of publication
Dagstuhl, Germany
Event location
Paris
Event date
Jan 1, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—