Geodesic
Logical complexity of induced subgraph isomorphism for certain families of graphs
Sbornik. Mathematics, Tome 212 (2021) no. 4, pp. 517-530 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We investigate the problem of the most efficient first-order definition of the property of containing an induced subgraph isomorphic to a given pattern graph, which is closely related to the time complexity of the decision problem for this property. We derive a series of new bounds for the minimum quantifier depth of a formula defining this property for pattern graphs on five vertices, as well as for disjoint unions of isomorphic complete multipartite graphs. Moreover, we prove that for any $\ell\geqslant 4$ there exists a graph on $\ell$ vertices and a first-order formula of quantifier depth at most $\ell-1$ that defines the property of containing an induced subgraph isomorphic to this graph. Bibliography: 12 titles.
Keywords: first-order formula, quantifier depth, induced subgraph, logical complexity. 
@article{SM_2021_212_4_a3,
     author = {M. E. Zhukovskii and E. D. Kudryavtsev and M. V. Makarov and A. S. Shlychkova},
     title = {Logical complexity of induced subgraph isomorphism for certain families of graphs},
     journal = {Sbornik. Mathematics},
     pages = {517--530},
     year = {2021},
     volume = {212},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2021_212_4_a3/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
AU  - E. D. Kudryavtsev
AU  - M. V. Makarov
AU  - A. S. Shlychkova
TI  - Logical complexity of induced subgraph isomorphism for certain families of graphs
JO  - Sbornik. Mathematics
PY  - 2021
SP  - 517
EP  - 530
VL  - 212
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/SM_2021_212_4_a3/
LA  - en
ID  - SM_2021_212_4_a3
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%A E. D. Kudryavtsev
%A M. V. Makarov
%A A. S. Shlychkova
%T Logical complexity of induced subgraph isomorphism for certain families of graphs
%J Sbornik. Mathematics
%D 2021
%P 517-530
%V 212
%N 4
%U http://geodesic.mathdoc.fr/item/SM_2021_212_4_a3/
%G en
%F SM_2021_212_4_a3
M. E. Zhukovskii; E. D. Kudryavtsev; M. V. Makarov; A. S. Shlychkova. Logical complexity of induced subgraph isomorphism for certain families of graphs. Sbornik. Mathematics, Tome 212 (2021) no. 4, pp. 517-530. http://geodesic.mathdoc.fr/item/SM_2021_212_4_a3/

[1] N. K. Vereschagin, A. Shen, Yazyki i ischisleniya, Lektsii po matematicheskoi logike i teorii algoritmov, 2, 4-e izd., ispr., MTsNMO, M., 2012, 240 pp. | Zbl

[2] M. E. Zhukovskii, A. M. Raigorodskii, “Random graphs: models and asymptotic characteristics”, Russian Math. Surveys, 70:1 (2015), 33–81 | DOI | DOI | MR | Zbl

[3] L. Libkin, Elements of finite model theory, Texts Theoret. Comput. Sci. EATCS Ser., Springer-Verlag, Berlin, 2004, xiv+315 pp. | DOI | MR | Zbl

[4] Jianer Chen, Xiuzhen Huang, I. A. Kanj, Ge Xia, “Strong computational lower bounds via parameterized complexity”, J. Comput. System Sci., 72:8 (2006), 1346–1367 | DOI | MR | Zbl

[5] J. Nešetřil, S. Poljak, “On the complexity of the subgraph problem”, Comment. Math. Univ. Carolin., 26:2 (1985), 415–419 | MR | Zbl

[6] F. Eisenbrand, F. Grandoni, “On the complexity of fixed parameter clique and dominating set”, Theoret. Comput. Sci., 326:1-3 (2004), 57–67 | DOI | MR | Zbl

[7] F. Le Gall, “Powers of tensors and fast matrix multiplication”, Proceedings of the 39th international symposium on symbolic and algebraic computation (ISSAC {'}14), ACM, New York, 2014, 296–303 | DOI | MR | Zbl

[8] O. Verbitsky, M. Zhukovskii, “On the first-order complexity of induced subgraph isomorphism”, Computer science logic, LIPIcs. Leibniz Int. Proc. Inform., 82, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, 40, 16 pp. | DOI | MR | Zbl

[9] S. Janson, T. Łuczak, A. Rucinski, Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience [John Wiley Sons], New York, 2000, xii+333 pp. | DOI | MR | Zbl

[10] O. Verbitsky, M. Zhukovskii, “The descriptive complexity of subgraph isomorphism without numerics”, Theory Comput. Syst., 63:4 (2019), 902–921 | DOI | MR | Zbl

[11] M. E. Zhukovskii, “On first-order definitions of subgraph isomorphism properties”, Dokl. Math., 96:2 (2017), 454–456 | DOI | DOI | MR | Zbl

[12] A. Ehrenfeucht, “An application of games to the completeness problem for formalized theories”, Fund. Math., 49 (1960/1961), 129–141 | DOI | MR | Zbl