<div class="csl-bib-body">
<div class="csl-entry">Ganian, R., Hliněný, P., Langer, A., Obdržálek, J., Rossmanith, P., & Sikdar, S. (2014). Lower bounds on the complexity of MSO₁ model-checking. <i>Journal of Computer and System Sciences</i>, <i>80</i>(1), 180–194. https://doi.org/10.1016/j.jcss.2013.07.005</div>
</div>
-
dc.identifier.issn
0022-0000
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/157455
-
dc.description.abstract
Recently, Kreutzer and Tazari proved a complexity lower-bound to the famous
MSO2 theorem of Courcelle-that MSO2 model-checking is not polynomial
(XP) wrt. the formula size as parameter for graph classes that are
subgraph-closed and whose tree-width is poly-logarithmically unbounded. We
prove that even MSO1 model-checking with a fixed set of vertex labels-i.e.,
without edge-set quantification-is not solvable in polynomial time (and even
not solvable in quasi-polynomial time) for fixed MSO1-formulas in such graph
classes. This also has an interesting consequence in the realm of digraph width
measures, strengthening upon recent results. Both the lower bounds hold modulo
a certain complexity-theoretic assumption, namely, the Exponential Time
Hypothesis (ETH) in the former case and the nonuniform ETH in the latter
case. Altogether, in comparison to Kreutzer and Tazari, we show a different
set of problems to be intractable, and our stronger complexity assumption of
nonuniform ETH slightly weakens assumptions on the graph class and simplifies
important lengthy parts of the former proof.
en
dc.description.sponsorship
Europäischer Forschungsrat (ERC)
-
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.relation.ispartof
Journal of Computer and System Sciences
-
dc.subject
Applied Mathematics
-
dc.subject
Theoretical Computer Science
-
dc.subject
Computational Theory and Mathematics
-
dc.subject
Computer Networks and Communications
-
dc.title
Lower bounds on the complexity of MSO₁ model-checking
en
dc.type
Artikel
de
dc.type
Article
en
dc.description.startpage
180
-
dc.description.endpage
194
-
dc.relation.grantno
239962
-
dc.relation.grantno
P 26696-N30
-
dc.type.category
Original Research Article
-
tuw.container.volume
80
-
tuw.container.issue
1
-
tuw.journal.peerreviewed
true
-
tuw.peerreviewed
true
-
wb.publication.intCoWork
International Co-publication
-
tuw.project.title
The Parameterized Complexity of Reasoning Problems
-
tuw.project.title
Exploiting New Types of Structure for Fixed Parameter Tractability
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
dcterms.isPartOf.title
Journal of Computer and System Sciences
-
tuw.publication.orgunit
E192-03 - Forschungsbereich Knowledge Based Systems
-
tuw.publisher.doi
10.1016/j.jcss.2013.07.005
-
dc.identifier.eissn
1090-2724
-
dc.description.numberOfPages
15
-
wb.sci
true
-
wb.sciencebranch
Informatik
-
wb.sciencebranch.oefos
1020
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_2df8fbb1
-
item.languageiso639-1
en
-
item.openairetype
research article
-
item.grantfulltext
none
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
Masaryk University, Czech Republic
-
crisitem.author.dept
RWTH Aachen University, Germany
-
crisitem.author.orcid
0000-0002-7762-8045
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.project.funder
Europäischer Forschungsrat (ERC)
-
crisitem.project.funder
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)