Отправить статью по E-mail Логическая сложность свойства наличия индуцированного подграфа, изоморфного данному, для некоторых семейств графов
- Авторы: Жуковский М.Е.1,2, Кудрявцев Е.Д.3, Макаров М.В.3, Шлычкова А.С.3
-
Учреждения:
- Лаборатория продвинутой комбинаторики и сетевых приложений, Московский физико-технический институт (национальный исследовательский университет)
- Московский центр фундаментальной и прикладной математики
- Московский физико-технический институт (национальный исследовательский университет)
- Выпуск: Том 212, № 4 (2021)
- Страницы: 76-90
- Раздел: Статьи
- URL: https://bakhtiniada.ru/0368-8666/article/view/133379
- DOI: https://doi.org/10.4213/sm9259
- ID: 133379
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
В настоящей работе изучается задача наиболее эффективной записи на языке первого порядка свойства наличия индуцированного подграфа, изоморфного заданному pattern-графу, тесно связанная с оцениванием временной сложности проверки такого свойства. Мы получили ряд новых оценок наименьшей кванторной глубины формулы, определяющей упомянутое свойство для pattern-графов на пяти вершинах, а также для дизъюнктных объединений изоморфных полных многодольных графов. Кроме того, мы доказали, что для любого $\ell\geq 4$ найдется граф на $\ell$ вершинах и формула первого порядка кванторной глубины не более $\ell-1$, записывающая свойство содержать индуцированный подграф, изоморфный этому графу.Библиография: 12 названий.
Ключевые слова
Об авторах
Максим Евгеньевич Жуковский
Лаборатория продвинутой комбинаторики и сетевых приложений, Московский физико-технический институт (национальный исследовательский университет); Московский центр фундаментальной и прикладной математики
Email: zhukmax@gmail.com
доктор физико-математических наук
Еремей Денисович Кудрявцев
Московский физико-технический институт (национальный исследовательский университет)
Email: keremey57@gmail.com
Михаил Владимирович Макаров
Московский физико-технический институт (национальный исследовательский университет)
Email: vbif-98@mail.ru
Александра Сергеевна Шлычкова
Московский физико-технический институт (национальный исследовательский университет)Список литературы
- Н. К. Верещагин, А. Шень, Языки и исчисления, Лекции по математической логике и теории алгоритмов, 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
Дополнительные файлы
