Are unique subgraphs not easier to find?
Research output: Contribution to journal › Article
Consider a pattern graph H with l edges, and a host graph G which may contain several occurrences of H. In , we claimed that the time complexity of the problems of finding an occurrence of H (if any) in G as well as that of the decision version of the problem are within a multiplicative factor O˜(l3) of the time complexity for the corresponding problem, where the host graph is guaranteed to contain at most one occurrence of a subgraph isomorphic to H, and the notation O˜ suppresses polylogarithmic in n factors. We show a counterexample to this too strong claim and correct it by providing an O˜((l(d−1)+2)l) bound on the multiplicative factor instead, where d is the maximum number of occurrences of H that can share the same edge in the input host graph. We provide also an analogous correction in the induced case when occurrences of induced subgraphs isomorphic to H are sought.
|Research areas and keywords||
Subject classification (UKÄ) – MANDATORY
|Number of pages||5|
|Journal||Information Processing Letters|
|Publication status||Published - 2018 Jun 1|