SIMPLIFIED ALGORITHMIC METATHEOREMS BEYOND MSO: TREEWIDTH AND NEIGHBORHOOD DIVERSITY

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10366349" target="_blank" >RIV/00216208:11320/17:10366349 - isvavai.cz</a>

Výsledek na webu

<a href="https://arxiv.org/abs/1703.00544" target="_blank" >https://arxiv.org/abs/1703.00544</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-68705-6_26" target="_blank" >10.1007/978-3-319-68705-6_26</a>

Jazyk výsledku

angličtina

Název v původním jazyce

SIMPLIFIED ALGORITHMIC METATHEOREMS BEYOND MSO: TREEWIDTH AND NEIGHBORHOOD DIVERSITY

Popis výsledku v původním jazyce

This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidth and graphs of bounded neighborhood diversity. A classical theorem of Courcelle states that any graph property definable in MSO is decidable in linear time on graphs of bounded treewidth. Algorithmic metatheorems like Courcelle&apos;s serve to generalize known positive results on various graph classes. We explore and extend three previously studied MSO extensions: global and local cardinality constraints (CardMSO and MSO-LCC) and optimizing a fair objective function (fairMSO). First, we show how these fragments relate to each other in expressive power and highlight their (non)linearity. On the side of neighborhood diversity, we show that combining the linear variants of local and global cardinality constraints is possible while keeping the linear runtime but removing linearity of either makes this impossible, and we provide a polynomial time algorithm for the hard case. Furthermore, we show that even the combination of the two most powerful fragments is solvable in polynomial time on graphs of bounded treewidth.

Název v anglickém jazyce

SIMPLIFIED ALGORITHMIC METATHEOREMS BEYOND MSO: TREEWIDTH AND NEIGHBORHOOD DIVERSITY

Popis výsledku anglicky

This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidth and graphs of bounded neighborhood diversity. A classical theorem of Courcelle states that any graph property definable in MSO is decidable in linear time on graphs of bounded treewidth. Algorithmic metatheorems like Courcelle&apos;s serve to generalize known positive results on various graph classes. We explore and extend three previously studied MSO extensions: global and local cardinality constraints (CardMSO and MSO-LCC) and optimizing a fair objective function (fairMSO). First, we show how these fragments relate to each other in expressive power and highlight their (non)linearity. On the side of neighborhood diversity, we show that combining the linear variants of local and global cardinality constraints is possible while keeping the linear runtime but removing linearity of either makes this impossible, and we provide a polynomial time algorithm for the hard case. Furthermore, we show that even the combination of the two most powerful fragments is solvable in polynomial time on graphs of bounded treewidth.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-319-68704-9

ISSN

0302-9743

e-ISSN

neuvedeno

Počet stran výsledku

14

Strana od-do

344-357

Název nakladatele

Springer International Publishing AG 2017

Místo vydání

Neuveden

Místo konání akce

Eindhoven

Datum konání akce

21. 6. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—