On the First-Order Complexity of Induced Subgraph Isomorphism

DOI10.4230/LIPIcs.CSL.2017.40zbMath1434.03092OpenAlexW2944700340MaRDI QIDQ5111210

Oleg Verbitsky, M. E. Zhukovskii

Publication date: 26 May 2020

Full work available at URL: https://arxiv.org/pdf/1704.02237.pdf

zbMATH Keywords

descriptive and computational complexityfinite-variable first-order logicinduced subgraph isomorphism problemquantifier depth and variable width

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)

Related Items

Infinite spectra of first-order properties for random hypergraphs, Logical complexity of induced subgraph isomorphism for certain families of graphs