The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Unique subgraphs are not easier to find

På svenska

Author

Summary, in English

Given a pattern graph H with l edges, and a host graph G guaranteed to contain at most one occurrence of a subgraph isomorphic to H, we show that the time complexity of the problem of finding such an occurrence (if any) in G as well as that of the decision version of the problem are within a multiplicative factor O(l) of the time complexity for the corresponding problem in the general case, when G may contain several occurrences of H. It follows that for pattern graphs of constant size, the aforementioned uniqueness guarantee cannot yield any asymptotic speed up. We also derive analogous results with the analogous multiplicative factor linear in the number of vertices of H in the induced case when occurrences of induced subgraphs of G isomorphic to H are sought.

Publishing year

2013

Language

English

Pages

1247-1253

Publication/Series

International Journal of Computer Mathematics

Volume

90

Issue

6

Document type

Journal article

Publisher

Taylor & Francis

Topic

  • Computer Science

Keywords

  • time complexity
  • induced subgraph isomorphism
  • isomorphism
  • unique subgraph occurrence
  • graph algorithms
  • subgraph

Status

Published

ISBN/ISSN/Other

  • ISSN: 1029-0265