On the first-order complexity of induced subgraph isomorphism

DOI10.4230/LIPICS.CSL.2017.40zbMATH Open1434.03092OpenAlexW2944700340MaRDI QIDQ5111210FDOQ5111210

Authors: Oleg Verbitsky, M. E. Zhukovskii 

Publication date: 26 May 2020

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

Recommendations

• On the first-order complexity of induced subgraph isomorphism
• Logical complexity of induced subgraph isomorphism for certain families of graphs
• First-order definitions of subgraph isomorphism through the adjacency and order relations
• Induced subgraph isomorphism: are some patterns substantially easier than others?

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cited In (5)

• Logical complexity of induced subgraph isomorphism for certain families of graphs
• First-order complexity of subgraph isomorphism via Kneser graphs
• Infinite spectra of first-order properties for random hypergraphs
• On the first-order complexity of induced subgraph isomorphism
• On first-order definitions of subgraph isomorphism properties

This page was built for publication: On the first-order complexity of induced subgraph isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111210)