A New Perspective on FO Model Checking of Dense Graph Classes
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F20%3A00114779" target="_blank" >RIV/00216224:14330/20:00114779 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1145/3383206" target="_blank" >http://dx.doi.org/10.1145/3383206</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3383206" target="_blank" >10.1145/3383206</a>
Alternative languages
Result language
angličtina
Original language name
A New Perspective on FO Model Checking of Dense Graph Classes
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA17-00837S" target="_blank" >GA17-00837S: Structural properties, parameterized tractability and hardness in combinatorial problems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
ACM Transactions on Computational Logic
ISSN
1529-3785
e-ISSN
1557-945X
Volume of the periodical
21
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
23
Pages from-to
„28:1“-„28:23“
UT code for WoS article
000586733900002
EID of the result in the Scopus database
2-s2.0-85096593679