Are unique subgraphs not easier to find?

作者：Kowaluk Miroslaw; Lingas Andrzej^*

来源：Information Processing Letters, 2018, 134: 57-61.

DOI：10.1016/j.ipl.2018.02.010

• Algorithms
• Subgraph isomorphism
• Induced subgraph isomorphism
• Unique subgraph occurrence
• Time complexity

Consider a pattern graph H with I edges, and a host graph G which may contain several occurrences of. H. In [15], 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) over tilde (I-3) 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) over tilde( ) suppresses polylogarithmic in n factors. We show a counterexample to this too strong claim and correct it by providing an (O) over tilde((I(d - 1) + 2)(i)) 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 Hare sought.

• 出版日期2018-6