Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism

DOI10.1145/3303881zbMATH Open1433.68162arXiv1802.02143OpenAlexW2963399986WikidataQ128124635 ScholiaQ128124635MaRDI QIDQ5222874FDOQ5222874

M. E. Zhukovskii, Oleg Verbitsky

Publication date: 4 July 2019

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Abstract: Let $v(F)$ denote the number of vertices in a fixed connected pattern graph $F$. We show an infinite family of patterns $F$ such that the existence of a subgraph isomorphic to $F$ is expressible by a first-order sentence of quantifier depth $frac23,v(F)+1$, assuming that the host graph is sufficiently large and connected. On the other hand, this is impossible for any $F$ with using less than $frac23,v(F)-2$ first-order variables.

Full work available at URL: https://arxiv.org/abs/1802.02143

Recommendations

• The descriptive complexity of subgraph isomorphism without numerics
• The descriptive complexity of subgraph isomorphism without numerics
• Logical complexity of induced subgraph isomorphism for certain families of graphs
• First-order complexity of subgraph isomorphism via Kneser graphs
• On first-order definitions of subgraph isomorphism properties

zbMATH Keywords

computational complexityfirst-order logicdescriptive complexitysubgraph isomorphism problemquantifier depthvariable width

Mathematics Subject Classification ID

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

Cited In (3)

• First-order definitions of subgraph isomorphism through the adjacency and order relations
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• The descriptive complexity of subgraph isomorphism without numerics

This page was built for publication: Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism

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