About: Lower Bounds on the Complexity of MSO

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Lower Bounds on the Complexity of MSO_1 Model-Checking Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	Kreutzer and Tazari proved in 2010 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 MSO1 model-checking with a fixed set of vertex labels---i.e., without edge-set quantification---is not solvable even in quasi-polynomial time for fixed MSO-formulas in such graph classes. 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. 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 greatly simplifies important lengthy parts of the former proof. Our result also has an interesting consequence in the realm of digraph width measures. Kreutzer and Tazari proved in 2010 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 MSO1 model-checking with a fixed set of vertex labels---i.e., without edge-set quantification---is not solvable even in quasi-polynomial time for fixed MSO-formulas in such graph classes. 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. 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 greatly simplifies important lengthy parts of the former proof. Our result also has an interesting consequence in the realm of digraph width measures. (en)
Title	Lower Bounds on the Complexity of MSO_1 Model-Checking Lower Bounds on the Complexity of MSO_1 Model-Checking (en)
skos:prefLabel	Lower Bounds on the Complexity of MSO_1 Model-Checking Lower Bounds on the Complexity of MSO_1 Model-Checking (en)
skos:notation	RIV/00216224:14330/14:00073428!RIV15-MSM-14330___
http://linked.open...avai/riv/aktivita	P S
http://linked.open...avai/riv/aktivity	P(GAP202/11/0196), S
http://linked.open...iv/cisloPeriodika	1
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Obdržálek, Jan Ganian, Robert Hliněný, Petr
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	26695
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/14:00073428
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Monadic Second-Order Logic; Treewidth; Lower Bounds; Exponential Time Hypothesis; Parameterized Complexity (en)
http://linked.open.../riv/klicoveSlovo	Exponential Time Hypothesis Lower Bounds Monadic Second-Order Logic Treewidth Parameterized Complexity
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[C1C2CC1AB879]
http://linked.open...i/riv/nazevZdroje	Journal of Computer and System Sciences
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	6 (xsd:int)
http://linked.open...vavai/riv/projekt	Well-structured combinatorial classes, width parameters, and design of efficient algorithms
http://linked.open...UplatneniVysledku	2014
http://linked.open...v/svazekPeriodika	80
http://linked.open...iv/tvurceVysledku	Ganian, Robert Hliněný, Petr Obdržálek, Jan Rossmanith, Peter Langer, Alexander Sikdar, Somnath
http://linked.open...ain/vavai/riv/wos	000325386500013
issn	0022-0000
number of pages	15 (xsd:int)
http://bibframe.org/vocab/doi	10.1016/j.jcss.2013.07.005
http://localhost/t...ganizacniJednotka	14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software