SIMPLIFIED ALGORITHMIC METATHEOREMS BEYOND MSO: TREEWIDTH AND NEIGHBORHOOD DIVERSITY

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
SIMPLIFIED ALGORITHMIC METATHEOREMS BEYOND MSO: TREEWIDTH AND NEIGHBORHOOD DIVERSITY
Original language description
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'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.
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)