What is it about?
Whether a graph or a network contains a pattern F as a subgraph can be described by a sentence of first-order logic. A direct description has quantifier depth v(F), where v(F) is the number of vertices in F. It is non-obvious whether or not this can be done more succinctly. We show that a first-order description of quantifier depth at most (2/3)v(F)+1 is always possible, and that this bound cannot be much better in general.
Featured Image
Photo by Alina Grubnyak on Unsplash
Why is it important?
The quantifier depth is an important measure of descriptive complexity of a graph property.
Perspectives
Succinct logical definitions can often be translated into efficient recognition algorithms. This motivates future research on this topic for related graph properties.
Oleg Verbitsky
Humboldt-Universitat zu Berlin
Read the Original
This page is a summary of: Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism, ACM Transactions on Computational Logic, April 2019, ACM (Association for Computing Machinery), DOI: 10.1145/3303881.
You can read the full text:
Contributors
The following have contributed to this page
