A New Perspective on FO Model Checking of Dense Graph Classes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00088546" target="_blank" >RIV/00216224:14330/16:00088546 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1145/2933575.2935314" target="_blank" >http://dx.doi.org/10.1145/2933575.2935314</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/2933575.2935314" target="_blank" >10.1145/2933575.2935314</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A New Perspective on FO Model Checking of Dense Graph Classes

Popis výsledku v původním jazyce

We study the FO model checking problem of dense graph classes, namely those which are FO-interpretable in some sparse graph classes. Note that if an input dense graph is given together with the corresponding FO interpretation in a sparse graph, one can easily solve the model checking problem using the existing algorithms for sparse graph classes. However, if the assumed interpretation is not given, then the situation is markedly harder. In this paper we give a structural characterization of graph classes which are FO interpretable in graph classes of bounded degree. This characterization allows us to efficiently compute such an interpretation for an input graph. As a consequence, we obtain an FPT algorithm for FO model checking of graph classes FO interpretable in graph classes of bounded degree. The approach we use to obtain these results may also be of independent interest.

Název v anglickém jazyce

A New Perspective on FO Model Checking of Dense Graph Classes

Popis výsledku anglicky

We study the FO model checking problem of dense graph classes, namely those which are FO-interpretable in some sparse graph classes. Note that if an input dense graph is given together with the corresponding FO interpretation in a sparse graph, one can easily solve the model checking problem using the existing algorithms for sparse graph classes. However, if the assumed interpretation is not given, then the situation is markedly harder. In this paper we give a structural characterization of graph classes which are FO interpretable in graph classes of bounded degree. This characterization allows us to efficiently compute such an interpretation for an input graph. As a consequence, we obtain an FPT algorithm for FO model checking of graph classes FO interpretable in graph classes of bounded degree. The approach we use to obtain these results may also be of independent interest.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA14-03501S" target="_blank" >GA14-03501S: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky</a><br>

Návaznosti

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

Rok uplatnění

2016

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

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science LICS2016

ISBN

9781450343916

ISSN

1043-6871

e-ISSN

—

Počet stran výsledku

9

Strana od-do

176-184

Název nakladatele

ACM

Místo vydání

New York, NY, USA

Místo konání akce

New York, NY, USA

Datum konání akce

5. 7. 2016

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

WRD - Celosvětová akce

Kód UT WoS článku

—