License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2017.40
URN: urn:nbn:de:0030-drops-76841
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7684/
Go to the corresponding LIPIcs Volume Portal


Verbitsky, Oleg ; Zhukovskii, Maksim

On the First-Order Complexity of Induced Subgraph Isomorphism

pdf-format:
LIPIcs-CSL-2017-40.pdf (0.5 MB)


Abstract

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.

BibTeX - Entry

@InProceedings{verbitsky_et_al:LIPIcs:2017:7684,
  author =	{Oleg Verbitsky and Maksim Zhukovskii},
  title =	{{On the First-Order Complexity of Induced Subgraph Isomorphism}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Valentin Goranko and Mads Dam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7684},
  URN =		{urn:nbn:de:0030-drops-76841},
  doi =		{10.4230/LIPIcs.CSL.2017.40},
  annote =	{Keywords: the induced subgraph isomorphism problem, descriptive and computational complexity, finite-variable first-order logic, quantifier depth and variable w}
}

Keywords: the induced subgraph isomorphism problem, descriptive and computational complexity, finite-variable first-order logic, quantifier depth and variable w
Seminar: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Issue Date: 2017
Date of publication: 14.08.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI