The Descriptive Complexity of Subgraph Isomorphism Without Numerics View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2017-05-06

AUTHORS

Oleg Verbitsky , Maksim Zhukovskii

ABSTRACT

Let F be a connected graph with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell $$\end{document} vertices. The existence of a subgraph isomorphic to F can be defined in first-order logic with quantifier depth no better than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell $$\end{document}, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_\ell $$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{\ell -1}$$\end{document}. We show that, for some F, the existence of an F subgraph in sufficiently large connected graphs is definable with quantifier depth \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell -3$$\end{document}. On the other hand, this is never possible with quantifier depth better than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell /2$$\end{document}. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some F be arbitrarily small comparing to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell $$\end{document} but never smaller than the treewidth of F.We also prove that any first-order definition of the existence of an induced subgraph isomorphic to F requires quantifier depth strictly more than the density of F, even over highly connected graphs. From this bound we derive a succinctness result for existential monadic second-order logic: A usage of just one monadic quantifier sometimes reduces the first-order quantifier depth at a super-recursive rate. More... »

PAGES

308-322

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-58747-9_27

DOI

http://dx.doi.org/10.1007/978-3-319-58747-9_27

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1085148876


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Informatik, Humboldt-Universit\u00e4t zu Berlin, Unter den Linden 6, 10099, Berlin, Germany", 
          "id": "http://www.grid.ac/institutes/grid.7468.d", 
          "name": [
            "Institut f\u00fcr Informatik, Humboldt-Universit\u00e4t zu Berlin, Unter den Linden 6, 10099, Berlin, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Verbitsky", 
        "givenName": "Oleg", 
        "id": "sg:person.01046052752.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01046052752.53"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Discrete Mathematics, Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow Region, Russia", 
          "id": "http://www.grid.ac/institutes/grid.18763.3b", 
          "name": [
            "Department of Discrete Mathematics, Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow Region, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhukovskii", 
        "givenName": "Maksim", 
        "id": "sg:person.011152672013.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2017-05-06", 
    "datePublishedReg": "2017-05-06", 
    "description": "Let F be a connected graph with \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\ell $$\\end{document} vertices. The existence of a subgraph isomorphic to F can be defined in first-order logic with quantifier depth no better than \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\ell $$\\end{document}, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$K_\\ell $$\\end{document} and \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$K_{\\ell -1}$$\\end{document}. We show that, for some F, the existence of an F subgraph in sufficiently large connected graphs is definable with quantifier depth \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\ell -3$$\\end{document}. On the other hand, this is never possible with quantifier depth better than \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\ell /2$$\\end{document}. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some F be arbitrarily small comparing to \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\ell $$\\end{document} but never smaller than the treewidth of\u00a0F.We also prove that any first-order definition of the existence of an induced subgraph isomorphic to F requires quantifier depth strictly more than the density of F, even over highly connected graphs. From this bound we derive a succinctness result for existential monadic second-order logic: A usage of just one monadic quantifier sometimes reduces the first-order quantifier depth at a super-recursive rate.", 
    "editor": [
      {
        "familyName": "Weil", 
        "givenName": "Pascal", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-58747-9_27", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-58746-2", 
        "978-3-319-58747-9"
      ], 
      "name": "Computer Science \u2013 Theory and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "rate", 
      "hand", 
      "definition", 
      "results", 
      "existence", 
      "usage", 
      "depth", 
      "density", 
      "monadic second-order logic", 
      "second-order logic", 
      "monadic quantifiers", 
      "first-order logic", 
      "formula", 
      "first-order definition", 
      "complexity", 
      "connected graph", 
      "descriptive complexity", 
      "logic", 
      "quantifiers", 
      "first-order formulas", 
      "vertices", 
      "isomorphic", 
      "induced subgraph", 
      "graph", 
      "subgraphs", 
      "isomorphism", 
      "complete graph", 
      "numerics", 
      "large connected graph", 
      "large treewidth", 
      "treewidth", 
      "succinctness results", 
      "subgraph isomorphism", 
      "subgraphs isomorphic", 
      "quantifier depth", 
      "smaller quantifier depth", 
      "existential monadic second-order logic", 
      "first-order quantifier depth", 
      "super-recursive rate"
    ], 
    "name": "The Descriptive Complexity of Subgraph Isomorphism Without Numerics", 
    "pagination": "308-322", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1085148876"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-58747-9_27"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-58747-9_27", 
      "https://app.dimensions.ai/details/publication/pub.1085148876"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T19:01", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_57.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-58747-9_27"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58747-9_27'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58747-9_27'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58747-9_27'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-58747-9_27'


 

This table displays all metadata directly associated to this object as RDF triples.

109 TRIPLES      23 PREDICATES      64 URIs      57 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-58747-9_27 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N260669d64e234f8c9d55b6193c0cc5e8
4 schema:datePublished 2017-05-06
5 schema:datePublishedReg 2017-05-06
6 schema:description Let F be a connected graph with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell $$\end{document} vertices. The existence of a subgraph isomorphic to F can be defined in first-order logic with quantifier depth no better than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell $$\end{document}, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_\ell $$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{\ell -1}$$\end{document}. We show that, for some F, the existence of an F subgraph in sufficiently large connected graphs is definable with quantifier depth \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell -3$$\end{document}. On the other hand, this is never possible with quantifier depth better than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell /2$$\end{document}. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some F be arbitrarily small comparing to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell $$\end{document} but never smaller than the treewidth of F.We also prove that any first-order definition of the existence of an induced subgraph isomorphic to F requires quantifier depth strictly more than the density of F, even over highly connected graphs. From this bound we derive a succinctness result for existential monadic second-order logic: A usage of just one monadic quantifier sometimes reduces the first-order quantifier depth at a super-recursive rate.
7 schema:editor Nb79580d801bb4a6ab9e7e6ed1878f05b
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N31278f8b3dc047299f25c941aa8265f8
12 schema:keywords complete graph
13 complexity
14 connected graph
15 definition
16 density
17 depth
18 descriptive complexity
19 existence
20 existential monadic second-order logic
21 first-order definition
22 first-order formulas
23 first-order logic
24 first-order quantifier depth
25 formula
26 graph
27 hand
28 induced subgraph
29 isomorphic
30 isomorphism
31 large connected graph
32 large treewidth
33 logic
34 monadic quantifiers
35 monadic second-order logic
36 numerics
37 quantifier depth
38 quantifiers
39 rate
40 results
41 second-order logic
42 smaller quantifier depth
43 subgraph isomorphism
44 subgraphs
45 subgraphs isomorphic
46 succinctness results
47 super-recursive rate
48 treewidth
49 usage
50 vertices
51 schema:name The Descriptive Complexity of Subgraph Isomorphism Without Numerics
52 schema:pagination 308-322
53 schema:productId N27985e6270e64bf28d3316d06b35c477
54 N5cc1fb438a944fea9d5f9d62dcd64d60
55 schema:publisher Nf850db9a48bd4a88812d92c3bad1bbd7
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085148876
57 https://doi.org/10.1007/978-3-319-58747-9_27
58 schema:sdDatePublished 2021-11-01T19:01
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher N9d749600bf174fb1ae6b8cd3777ac61d
61 schema:url https://doi.org/10.1007/978-3-319-58747-9_27
62 sgo:license sg:explorer/license/
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N260669d64e234f8c9d55b6193c0cc5e8 rdf:first sg:person.01046052752.53
66 rdf:rest N386ea61830c9404eb3de8aab7ce444a8
67 N27985e6270e64bf28d3316d06b35c477 schema:name dimensions_id
68 schema:value pub.1085148876
69 rdf:type schema:PropertyValue
70 N31278f8b3dc047299f25c941aa8265f8 schema:isbn 978-3-319-58746-2
71 978-3-319-58747-9
72 schema:name Computer Science – Theory and Applications
73 rdf:type schema:Book
74 N386ea61830c9404eb3de8aab7ce444a8 rdf:first sg:person.011152672013.96
75 rdf:rest rdf:nil
76 N5cc1fb438a944fea9d5f9d62dcd64d60 schema:name doi
77 schema:value 10.1007/978-3-319-58747-9_27
78 rdf:type schema:PropertyValue
79 N9d749600bf174fb1ae6b8cd3777ac61d schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 Nb79580d801bb4a6ab9e7e6ed1878f05b rdf:first Nc4de1b34096b450896bb8945e725e0d3
82 rdf:rest rdf:nil
83 Nc4de1b34096b450896bb8945e725e0d3 schema:familyName Weil
84 schema:givenName Pascal
85 rdf:type schema:Person
86 Nf850db9a48bd4a88812d92c3bad1bbd7 schema:name Springer Nature
87 rdf:type schema:Organisation
88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
89 schema:name Information and Computing Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
92 schema:name Computation Theory and Mathematics
93 rdf:type schema:DefinedTerm
94 sg:person.01046052752.53 schema:affiliation grid-institutes:grid.7468.d
95 schema:familyName Verbitsky
96 schema:givenName Oleg
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01046052752.53
98 rdf:type schema:Person
99 sg:person.011152672013.96 schema:affiliation grid-institutes:grid.18763.3b
100 schema:familyName Zhukovskii
101 schema:givenName Maksim
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96
103 rdf:type schema:Person
104 grid-institutes:grid.18763.3b schema:alternateName Department of Discrete Mathematics, Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow Region, Russia
105 schema:name Department of Discrete Mathematics, Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow Region, Russia
106 rdf:type schema:Organization
107 grid-institutes:grid.7468.d schema:alternateName Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099, Berlin, Germany
108 schema:name Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099, Berlin, Germany
109 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...