A New Perspective on FO Model Checking of Dense Graph Classes

GAJARSKÝ, Jakub, Petr HLINĚNÝ, Daniel LOKSHTANOV, Jan OBDRŽÁLEK a M S RAMANUJAN. A New Perspective on FO Model Checking of Dense Graph Classes. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science LICS2016. New York, NY, USA: ACM, 2016, s. 176-184. ISBN 978-1-4503-4391-6. Dostupné z: https://dx.doi.org/10.1145/2933575.2935314.

Základní údaje

Originální název

A New Perspective on FO Model Checking of Dense Graph Classes

Autoři

GAJARSKÝ, Jakub (703 Slovensko, domácí), Petr HLINĚNÝ (203 Česká republika, garant, domácí), Daniel LOKSHTANOV (578 Norsko), Jan OBDRŽÁLEK (203 Česká republika, domácí) a M S RAMANUJAN (356 Indie)

Vydání

New York, NY, USA, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science LICS2016, od s. 176-184, 9 s. 2016

Nakladatel

ACM

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

URL

Kód RIV

RIV/00216224:14330/16:00088546

Organizační jednotka

Fakulta informatiky

ISBN

978-1-4503-4391-6

ISSN

DOI

http://dx.doi.org/10.1145/2933575.2935314

UT WoS

000387609200018

Klíčová slova anglicky

FO Logic; Model-Checking; Logic Interpretations; Sparse Graph Classes; Parameterized Complexity

Štítky

core_A, firank_1, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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.

Česky

Podáváme strukturální charakteristiku a algoritmicky efektivní zpracování tříd grafů, které mají FO interpretaci v grafech omezených stupňů.

---

Návaznosti

GA14-03501S, projekt VaV	Název: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky Investor: Grantová agentura ČR, Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
MUNI/A/0935/2015, interní kód MU	Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU) Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/0945/2015, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V. Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty