Unique subgraphs are not easier to find

Abstract

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.

Keywords:

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

2010 AMS Subject Classifications :

• 68W01
• 68W40
• 68Q25
• 68R10
• 05C50

Acknowledgements

The authors are grateful to referees for valuable comments on a preliminary version of the paper. The research of the first author has been supported by the grant no.∖N206 566740 of the National Science Center while that of the second and third authors in part by the Swedish Research Council grant 621-2008-4649.