A New Perspective on FO Model Checking of Dense Graph Classes

D 2016

A New Perspective on FO Model Checking of Dense Graph Classes

GAJARSKÝ, Jakub, Petr HLINĚNÝ, Daniel LOKSHTANOV, Jan OBDRŽÁLEK, M S RAMANUJAN et. al.

Basic information

Original name

A New Perspective on FO Model Checking of Dense Graph Classes

Authors

GAJARSKÝ, Jakub (703 Slovakia, belonging to the institution), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution), Daniel LOKSHTANOV (578 Norway), Jan OBDRŽÁLEK (203 Czech Republic, belonging to the institution) and M S RAMANUJAN (356 India)

Edition

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

Publisher

ACM

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

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

Publication form

printed version "print"

References:

URL

RIV identification code

RIV/00216224:14330/16:00088546

Organization unit

Faculty of Informatics

ISBN

978-1-4503-4391-6

ISSN

DOI

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

UT WoS

000387609200018

Keywords in English

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

Abstract

ORIG CZ

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.

In Czech

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

Links

GA14-03501S, research and development project

Name: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky

Investor: Czech Science Foundation

MUNI/A/0935/2015, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKOMU)

Investor: Masaryk University, Category A

MUNI/A/0945/2015, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V.

Investor: Masaryk University, Category A

Citovat

GAJARSKÝ, Jakub, Petr HLINĚNÝ, Daniel LOKSHTANOV, Jan OBDRŽÁLEK and 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, p. 176-184. ISBN 978-1-4503-4391-6. Available from: https://dx.doi.org/10.1145/2933575.2935314.

@inproceedings{1367542,
   author = {Gajarský, Jakub and Hliněný, Petr and Lokshtanov, Daniel and Obdržálek, Jan and Ramanujan, M S},
   address = {New York, NY, USA},
   booktitle = {Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science LICS2016},
   doi = {http://dx.doi.org/10.1145/2933575.2935314},
   keywords = {FO Logic; Model-Checking; Logic Interpretations; Sparse Graph Classes; Parameterized Complexity},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {New York, NY, USA},
   isbn = {978-1-4503-4391-6},
   pages = {176-184},
   publisher = {ACM},
   title = {A New Perspective on FO Model Checking of Dense Graph Classes},
   url = {http://lics.rwth-aachen.de/lics16/},
   year = {2016}
}

TY  - JOUR
ID  - 1367542
AU  - Gajarský, Jakub - Hliněný, Petr - Lokshtanov, Daniel - Obdržálek, Jan - Ramanujan, M S
PY  - 2016
TI  - A New Perspective on FO Model Checking of Dense Graph Classes
PB  - ACM
CY  - New York, NY, USA
SN  - 9781450343916
KW  - FO Logic
KW  - Model-Checking
KW  - Logic Interpretations
KW  - Sparse Graph Classes
KW  - Parameterized Complexity
UR  - http://lics.rwth-aachen.de/lics16/
N2  - 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.
ER  -

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

Detailed Information on Publication Record