2026-07-24T06:30:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7684 2024-03-06T10:40:48Z ddc:004 open_access

On the First-Order Complexity of Induced Subgraph Isomorphism Verbitsky, Oleg Zhukovskii, Maksim the induced subgraph isomorphism problem descriptive and computational complexity finite-variable first-order logic quantifier depth and variable w Given a graph F, let I(F) be the class of graphs containing F as an induced subgraph. Let W[F] denote the minimum k such that I(F) is definable in k-variable first-order logic. The recognition problem of I(F), known as Induced Subgraph Isomorphism (for the pattern graph F), is solvable in time O(n^{W[F]}). Motivated by this fact, we are interested in determining or estimating the value of W[F]. Using Olariu's characterization of paw-free graphs, we show that I(K_3+e) is definable by a first-order sentence of quantifier depth 3, where K_3+e denotes the paw graph. This provides an example of a graph F with W[F] strictly less than the number of vertices in F. On the other hand, we prove that W[F]=4 for all F on 4 vertices except the paw graph and its complement. If F is a graph on t vertices, we prove a general lower bound W[F]>(1/2-o(1))t, where the function in the little-o notation approaches 0 as t increases. This bound holds true even for a related parameter W^*[F], which is defined as the minimum k such that I(F) is definable in the k-variable infinitary logic. We show that W^*[F] can be strictly less than W[F]. Specifically, W^*[P_4]=3 for P_4 being the path graph on 4 vertices. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oleg Verbitsky and Maksim Zhukovskii 2017 Is Part Of LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2017.40 urn:nbn:de:0030-drops-76841 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.40 eng https://creativecommons.org/licenses/by/3.0/legalcode