The Descriptive Complexity of Subgraph Isomorphism Without Numerics View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2018-04-30

AUTHORS

Oleg Verbitsky, Maksim Zhukovskii

ABSTRACT

Let F be a connected graph with ℓ vertices. The existence of a subgraph isomorphic to F can be defined in first-order logic with quantifier depth no better than ℓ, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs Kℓ and Kℓ− 1. We show that, for some F, the existence of an F subgraph in sufficiently large connected graphs is definable with quantifier depth ℓ − 3. On the other hand, this is never possible with quantifier depth better than ℓ/2. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some F be arbitrarily small comparing to ℓ but never smaller than the treewidth of F. Moreover, the definitions over highly connected graphs require quantifier depth strictly more than the density of F. Finally, we determine the exact values of these descriptive complexity parameters for all connected pattern graphs F on 4 vertices. More... »

PAGES

902-921

References to SciGraph publications

  • 2004. Elements of Finite Model Theory in NONE
  • 2013. A Short Tutorial on Order-Invariant First-Order Logic in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • 2015-09-05. Is Polynomial Time Choiceless? in FIELDS OF LOGIC AND COMPUTATION II
  • 2017-05-06. The Descriptive Complexity of Subgraph Isomorphism Without Numerics in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • 2010-05-10. k-Subgraph Isomorphism on AC0 Circuits in COMPUTATIONAL COMPLEXITY
  • 2007-02. Some Recent Progress and Applications in Graph Minor Theory in GRAPHS AND COMBINATORICS
  • 1999. Descriptive Complexity in NONE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-018-9864-3

    DOI

    http://dx.doi.org/10.1007/s00224-018-9864-3

    DIMENSIONS

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


    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, D-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, D-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": "Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology, Moscow, Russia", 
              "id": "http://www.grid.ac/institutes/grid.18763.3b", 
              "name": [
                "Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology, Moscow, 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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-319-23534-9_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000670911", 
              "https://doi.org/10.1007/978-3-319-23534-9_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00037-010-0288-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043395094", 
              "https://doi.org/10.1007/s00037-010-0288-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-07003-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046929489", 
              "https://doi.org/10.1007/978-3-662-07003-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-58747-9_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1085148876", 
              "https://doi.org/10.1007/978-3-319-58747-9_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-0539-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019353558", 
              "https://doi.org/10.1007/978-1-4612-0539-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00373-006-0684-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001076540", 
              "https://doi.org/10.1007/s00373-006-0684-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-38536-0_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047348372", 
              "https://doi.org/10.1007/978-3-642-38536-0_10"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-04-30", 
        "datePublishedReg": "2018-04-30", 
        "description": "Let F be a connected graph with \u2113 vertices. The existence of a subgraph isomorphic to F can be defined in first-order logic with quantifier depth no better than \u2113, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs K\u2113 and K\u2113\u2212\u20091. We show that, for some F, the existence of an F subgraph in sufficiently large connected graphs is definable with quantifier depth \u2113 \u2212\u20093. On the other hand, this is never possible with quantifier depth better than \u2113/2. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some F be arbitrarily small comparing to \u2113 but never smaller than the treewidth of F. Moreover, the definitions over highly connected graphs require quantifier depth strictly more than the density of F. Finally, we determine the exact values of these descriptive complexity parameters for all connected pattern graphs F on 4 vertices.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-018-9864-3", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.6741220", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.6751875", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "63"
          }
        ], 
        "keywords": [
          "first-order logic", 
          "large connected graph", 
          "connected graph", 
          "subgraph isomorphism", 
          "first-order formulas", 
          "large treewidth", 
          "descriptive complexity", 
          "complexity parameters", 
          "graph", 
          "treewidth", 
          "small comparing", 
          "subgraphs isomorphic", 
          "quantifier depth", 
          "complete graph", 
          "vertices", 
          "subgraphs", 
          "complexity", 
          "logic", 
          "definition", 
          "exact values", 
          "numerics", 
          "comparing", 
          "isomorphism", 
          "hand", 
          "parameters", 
          "isomorphic", 
          "formula", 
          "depth", 
          "graph F", 
          "existence", 
          "values", 
          "Moreover", 
          "density", 
          "smaller quantifier depth", 
          "descriptive complexity parameters", 
          "connected pattern graphs F", 
          "pattern graphs F"
        ], 
        "name": "The Descriptive Complexity of Subgraph Isomorphism Without Numerics", 
        "pagination": "902-921", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1103686578"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-018-9864-3"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-018-9864-3", 
          "https://app.dimensions.ai/details/publication/pub.1103686578"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:40", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_760.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-018-9864-3"
      }
    ]
     

    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/s00224-018-9864-3'

    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/s00224-018-9864-3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-018-9864-3'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-018-9864-3'


     

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

    137 TRIPLES      22 PREDICATES      69 URIs      54 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-018-9864-3 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nfb93d043a2b24b6a8a9adb54e5502d92
    4 schema:citation sg:pub.10.1007/978-1-4612-0539-5
    5 sg:pub.10.1007/978-3-319-23534-9_11
    6 sg:pub.10.1007/978-3-319-58747-9_27
    7 sg:pub.10.1007/978-3-642-38536-0_10
    8 sg:pub.10.1007/978-3-662-07003-1
    9 sg:pub.10.1007/s00037-010-0288-y
    10 sg:pub.10.1007/s00373-006-0684-x
    11 schema:datePublished 2018-04-30
    12 schema:datePublishedReg 2018-04-30
    13 schema:description Let F be a connected graph with ℓ vertices. The existence of a subgraph isomorphic to F can be defined in first-order logic with quantifier depth no better than ℓ, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs Kℓ and Kℓ− 1. We show that, for some F, the existence of an F subgraph in sufficiently large connected graphs is definable with quantifier depth ℓ − 3. On the other hand, this is never possible with quantifier depth better than ℓ/2. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some F be arbitrarily small comparing to ℓ but never smaller than the treewidth of F. Moreover, the definitions over highly connected graphs require quantifier depth strictly more than the density of F. Finally, we determine the exact values of these descriptive complexity parameters for all connected pattern graphs F on 4 vertices.
    14 schema:genre article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree true
    17 schema:isPartOf Ne5e0a569ea8d42679205326fb50eda2d
    18 Nef62a52bfdb94998837933199bad4a3c
    19 sg:journal.1052098
    20 schema:keywords Moreover
    21 comparing
    22 complete graph
    23 complexity
    24 complexity parameters
    25 connected graph
    26 connected pattern graphs F
    27 definition
    28 density
    29 depth
    30 descriptive complexity
    31 descriptive complexity parameters
    32 exact values
    33 existence
    34 first-order formulas
    35 first-order logic
    36 formula
    37 graph
    38 graph F
    39 hand
    40 isomorphic
    41 isomorphism
    42 large connected graph
    43 large treewidth
    44 logic
    45 numerics
    46 parameters
    47 pattern graphs F
    48 quantifier depth
    49 small comparing
    50 smaller quantifier depth
    51 subgraph isomorphism
    52 subgraphs
    53 subgraphs isomorphic
    54 treewidth
    55 values
    56 vertices
    57 schema:name The Descriptive Complexity of Subgraph Isomorphism Without Numerics
    58 schema:pagination 902-921
    59 schema:productId N3d7ab9e9dee64ef3887e9448bc4c6d46
    60 N917f92ada28e4dc1b1e8eb1aa54f06da
    61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103686578
    62 https://doi.org/10.1007/s00224-018-9864-3
    63 schema:sdDatePublished 2021-12-01T19:40
    64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    65 schema:sdPublisher N472db53d12d741e09511ec1f98384353
    66 schema:url https://doi.org/10.1007/s00224-018-9864-3
    67 sgo:license sg:explorer/license/
    68 sgo:sdDataset articles
    69 rdf:type schema:ScholarlyArticle
    70 N3d7ab9e9dee64ef3887e9448bc4c6d46 schema:name dimensions_id
    71 schema:value pub.1103686578
    72 rdf:type schema:PropertyValue
    73 N472db53d12d741e09511ec1f98384353 schema:name Springer Nature - SN SciGraph project
    74 rdf:type schema:Organization
    75 N7e6e76911d314144bfa6c4f6a6f97ef3 rdf:first sg:person.011152672013.96
    76 rdf:rest rdf:nil
    77 N917f92ada28e4dc1b1e8eb1aa54f06da schema:name doi
    78 schema:value 10.1007/s00224-018-9864-3
    79 rdf:type schema:PropertyValue
    80 Ne5e0a569ea8d42679205326fb50eda2d schema:volumeNumber 63
    81 rdf:type schema:PublicationVolume
    82 Nef62a52bfdb94998837933199bad4a3c schema:issueNumber 4
    83 rdf:type schema:PublicationIssue
    84 Nfb93d043a2b24b6a8a9adb54e5502d92 rdf:first sg:person.01046052752.53
    85 rdf:rest N7e6e76911d314144bfa6c4f6a6f97ef3
    86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    87 schema:name Information and Computing Sciences
    88 rdf:type schema:DefinedTerm
    89 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Computation Theory and Mathematics
    91 rdf:type schema:DefinedTerm
    92 sg:grant.6741220 http://pending.schema.org/fundedItem sg:pub.10.1007/s00224-018-9864-3
    93 rdf:type schema:MonetaryGrant
    94 sg:grant.6751875 http://pending.schema.org/fundedItem sg:pub.10.1007/s00224-018-9864-3
    95 rdf:type schema:MonetaryGrant
    96 sg:journal.1052098 schema:issn 1432-4350
    97 1433-0490
    98 schema:name Theory of Computing Systems
    99 schema:publisher Springer Nature
    100 rdf:type schema:Periodical
    101 sg:person.01046052752.53 schema:affiliation grid-institutes:grid.7468.d
    102 schema:familyName Verbitsky
    103 schema:givenName Oleg
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01046052752.53
    105 rdf:type schema:Person
    106 sg:person.011152672013.96 schema:affiliation grid-institutes:grid.18763.3b
    107 schema:familyName Zhukovskii
    108 schema:givenName Maksim
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96
    110 rdf:type schema:Person
    111 sg:pub.10.1007/978-1-4612-0539-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019353558
    112 https://doi.org/10.1007/978-1-4612-0539-5
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/978-3-319-23534-9_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000670911
    115 https://doi.org/10.1007/978-3-319-23534-9_11
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/978-3-319-58747-9_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085148876
    118 https://doi.org/10.1007/978-3-319-58747-9_27
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-642-38536-0_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047348372
    121 https://doi.org/10.1007/978-3-642-38536-0_10
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/978-3-662-07003-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046929489
    124 https://doi.org/10.1007/978-3-662-07003-1
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/s00037-010-0288-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1043395094
    127 https://doi.org/10.1007/s00037-010-0288-y
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/s00373-006-0684-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1001076540
    130 https://doi.org/10.1007/s00373-006-0684-x
    131 rdf:type schema:CreativeWork
    132 grid-institutes:grid.18763.3b schema:alternateName Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology, Moscow, Russia
    133 schema:name Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology, Moscow, Russia
    134 rdf:type schema:Organization
    135 grid-institutes:grid.7468.d schema:alternateName Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099, Berlin, Germany
    136 schema:name Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099, Berlin, Germany
    137 rdf:type schema:Organization
     




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


    ...