View in EDS

Induced subgraph isomorphism: Are some patterns substantially easier than others?

Saved in:
Bibliographic Details
Title: Induced subgraph isomorphism: Are some patterns substantially easier than others?
Authors: Floderus, Peter1 Peter.Floderus@maths.lth.se, Kowaluk, Mirosław2 kowaluk@mimuw.edu.pl, Lingas, Andrzej3 Andrzej.Lingas@cs.lth.se, Lundell, Eva-Marta3 Eva-Marta.Lundell@cs.lth.se
Source: Theoretical Computer Science. Nov2015, Vol. 605, p119-128. 10p.
Subjects: Subgraphs, Isomorphism (Mathematics), Computational complexity, Topology, Set theory
Abstract: The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced subgraph of fixed size can be substantially easier to detect or count than an independent set of related size. We show that any fixed pattern graph having a maximum independent set of size k that is disjoint from other maximum independent sets is not easier to detect as an induced subgraph than an independent set of size k . It follows in particular that an induced path on 2 k − 1 vertices is not easier to detect than an independent set on k vertices, and that an induced cycle on 2 k vertices is not easier to detect than an independent set on k vertices. In view of linear time upper bounds on the detection of induced path of length two and three, our lower bound is tight. Similar corollaries hold for the detection of induced complete bipartite graphs and an induced paw and its generalizations. We show also that for an arbitrary pattern graph H on k vertices with no isolated vertices, there is a simple subdivision of H , resulting from splitting each edge into a path of length four and attaching a distinct path of length three at each vertex of degree one, that is not easier to detect or count than an independent set on k vertices, respectively. Next, we show that the so-called diamond and its generalizations on k vertices are not easier to detect as induced subgraphs than an independent set on three vertices or an independent set on k vertices, respectively. For C 4 , we give a weaker evidence of its hardness in terms of an independent set on three vertices. Finally, we derive several results relating the complexity of the edge-colored variant of induced subgraph isomorphism to that of the standard variant. [ABSTRACT FROM AUTHOR]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 110408681
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Induced subgraph isomorphism: Are some patterns substantially easier than others?
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Floderus%2C+Peter%22">Floderus, Peter</searchLink><relatesTo>1</relatesTo><i> Peter.Floderus@maths.lth.se</i><br /><searchLink fieldCode="AR" term="%22Kowaluk%2C+Mirosław%22">Kowaluk, Mirosław</searchLink><relatesTo>2</relatesTo><i> kowaluk@mimuw.edu.pl</i><br /><searchLink fieldCode="AR" term="%22Lingas%2C+Andrzej%22">Lingas, Andrzej</searchLink><relatesTo>3</relatesTo><i> Andrzej.Lingas@cs.lth.se</i><br /><searchLink fieldCode="AR" term="%22Lundell%2C+Eva-Marta%22">Lundell, Eva-Marta</searchLink><relatesTo>3</relatesTo><i> Eva-Marta.Lundell@cs.lth.se</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink>. Nov2015, Vol. 605, p119-128. 10p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Subgraphs%22">Subgraphs</searchLink><br /><searchLink fieldCode="DE" term="%22Isomorphism+%28Mathematics%29%22">Isomorphism (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Topology%22">Topology</searchLink><br /><searchLink fieldCode="DE" term="%22Set+theory%22">Set theory</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced subgraph of fixed size can be substantially easier to detect or count than an independent set of related size. We show that any fixed pattern graph having a maximum independent set of size k that is disjoint from other maximum independent sets is not easier to detect as an induced subgraph than an independent set of size k . It follows in particular that an induced path on 2 k − 1 vertices is not easier to detect than an independent set on k vertices, and that an induced cycle on 2 k vertices is not easier to detect than an independent set on k vertices. In view of linear time upper bounds on the detection of induced path of length two and three, our lower bound is tight. Similar corollaries hold for the detection of induced complete bipartite graphs and an induced paw and its generalizations. We show also that for an arbitrary pattern graph H on k vertices with no isolated vertices, there is a simple subdivision of H , resulting from splitting each edge into a path of length four and attaching a distinct path of length three at each vertex of degree one, that is not easier to detect or count than an independent set on k vertices, respectively. Next, we show that the so-called diamond and its generalizations on k vertices are not easier to detect as induced subgraphs than an independent set on three vertices or an independent set on k vertices, respectively. For C 4 , we give a weaker evidence of its hardness in terms of an independent set on three vertices. Finally, we derive several results relating the complexity of the edge-colored variant of induced subgraph isomorphism to that of the standard variant. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=110408681
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.tcs.2015.09.001
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 10
        StartPage: 119
    Subjects:
      – SubjectFull: Subgraphs
        Type: general
      – SubjectFull: Isomorphism (Mathematics)
        Type: general
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Topology
        Type: general
      – SubjectFull: Set theory
        Type: general
    Titles:
      – TitleFull: Induced subgraph isomorphism: Are some patterns substantially easier than others?
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Floderus, Peter
      – PersonEntity:
          Name:
            NameFull: Kowaluk, Mirosław
      – PersonEntity:
          Name:
            NameFull: Lingas, Andrzej
      – PersonEntity:
          Name:
            NameFull: Lundell, Eva-Marta
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 09
              M: 11
              Text: Nov2015
              Type: published
              Y: 2015
          Identifiers:
            – Type: issn-print
              Value: 03043975
          Numbering:
            – Type: volume
              Value: 605
          Titles:
            – TitleFull: Theoretical Computer Science
              Type: main
ResultId 1