Logical complexity of induced subgraph isomorphism for certain families of graphs

DOI10.1070/SM9259zbMath1468.05189OpenAlexW3126911753MaRDI QIDQ5003303

Aleksandra S. Shlychkova, Mikhail Makarov, Eremei D. Kudryavtsev, M. E. Zhukovskii

Publication date: 21 July 2021

Published in: Sbornik: Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1070/sm9259

zbMATH Keywords

induced subgraphlogical complexityfirst-order formulaquantifier depth

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On first-order definitions of subgraph isomorphism properties
• On the complexity of fixed parameter clique and dominating set
• Elements of finite model theory.
• Strong computational lower bounds via parameterized complexity
• An application of games to the completeness problem for formalized theories
• Powers of tensors and fast matrix multiplication
• On the First-Order Complexity of Induced Subgraph Isomorphism
• Random graphs: models and asymptotic characteristics
• The descriptive complexity of subgraph isomorphism without numerics

This page was built for publication: Logical complexity of induced subgraph isomorphism for certain families of graphs