Email this article Logical complexity of induced subgraph isomorphism for certain families of graphs
- Authors: Zhukovskii M.E.1,2, Kudryavtsev E.D.3, Makarov M.V.3, Shlychkova A.S.3
-
Affiliations:
- Advanced Combinatorics and Networking Lab, Moscow Institute of Physics and Technology (National Research University)
- Moscow Center for Fundamental and Applied Mathematics
- Moscow Institute of Physics and Technology (National Research University)
- Issue: Vol 212, No 4 (2021)
- Pages: 76-90
- Section: Articles
- URL: https://journals.rcsi.science/0368-8666/article/view/133379
- DOI: https://doi.org/10.4213/sm9259
- ID: 133379
Cite item
Open Access
Access granted
Subscription Access
Abstract
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\geq 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.
About the authors
Maksim Evgen'evich Zhukovskii
Advanced Combinatorics and Networking Lab, Moscow Institute of Physics and Technology (National Research University); Moscow Center for Fundamental and Applied Mathematics
Email: zhukmax@gmail.com
Doctor of physico-mathematical sciences
Eremei Denisovich Kudryavtsev
Moscow Institute of Physics and Technology (National Research University)
Email: keremey57@gmail.com
Mikhail Vladimirovich Makarov
Moscow Institute of Physics and Technology (National Research University)
Email: vbif-98@mail.ru
Aleksandra Sergeevna Shlychkova
Moscow Institute of Physics and Technology (National Research University)References
- Н. К. Верещагин, А. Шень, Языки и исчисления, Лекции по математической логике и теории алгоритмов, 2, 4-е изд., испр., МЦНМО, М., 2012, 240 с.
- М. Е. Жуковский, А. М. Райгородский, “Случайные графы: модели и предельные характеристики”, УМН, 70:1(421) (2015), 35–88
- L. Libkin, Elements of finite model theory, Texts Theoret. Comput. Sci. EATCS Ser., Springer-Verlag, Berlin, 2004, xiv+315 pp.
- 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
- J. Nešetřil, S. Poljak, “On the complexity of the subgraph problem”, Comment. Math. Univ. Carolin., 26:2 (1985), 415–419
- F. Eisenbrand, F. Grandoni, “On the complexity of fixed parameter clique and dominating set”, Theoret. Comput. Sci., 326:1-3 (2004), 57–67
- 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
- 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.
- 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.
- O. Verbitsky, M. Zhukovskii, “The descriptive complexity of subgraph isomorphism without numerics”, Theory Comput. Syst., 63:4 (2019), 902–921
- М. Е. Жуковский, “Запись свойства существования изоморфного подграфа на языке первого порядка”, Докл. РАН, 476:3 (2017), 256–259
- A. Ehrenfeucht, “An application of games to the completeness problem for formalized theories”, Fund. Math., 49 (1960/1961), 129–141
Supplementary files
