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

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:

Read

Contributors

The following have contributed to this page