On the First-Order Complexity of Subgraph Isomorphism

ABSTRACT. Let F be a fixed pattern graph with k vertices. The Subgraph Isomorphism problem asks whether a given host graph G contains a subgraph isomorphic to F. In the induced version of the problem, the question is whether G has an induced copy of F. Each of the two problems can be expressed by a first-order sentence of quantifier depth k. We investigate the question whether this can be done more succinctly with respect to the quantifier depth and the variable width. A more detailed 2-page abstract is uploaded as a pdf file. This is joint work with Maksim Zhukovskii.

Authors

• Oleg Verbitsky

Keywords

No keywords are indexed for this paper.