Are unique subgraphs not easier to find?
(2018) In Information Processing Letters 134. p.5761 Abstract
Consider a pattern graph H with l 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˜(l^{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˜ 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... (More)
Consider a pattern graph H with l 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˜(l^{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˜ 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.
(Less)
 author
 Kowaluk, Mirosław and Lingas, Andrzej ^{LU}
 organization
 publishing date
 20180601
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Algorithms, Induced subgraph isomorphism, Subgraph isomorphism, Time complexity, Unique subgraph occurrence
 in
 Information Processing Letters
 volume
 134
 pages
 5 pages
 publisher
 Elsevier
 external identifiers

 scopus:85042002072
 ISSN
 00200190
 DOI
 10.1016/j.ipl.2018.02.010
 language
 English
 LU publication?
 yes
 id
 1fede768d0954c89b7ae8c84e13b2682
 date added to LUP
 20180305 07:55:39
 date last changed
 20180529 11:12:28
@article{1fede768d0954c89b7ae8c84e13b2682, abstract = {<p>Consider a pattern graph H with l 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˜(l<sup>3</sup>) 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)<sup>l</sup>) 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.</p>}, author = {Kowaluk, Mirosław and Lingas, Andrzej}, issn = {00200190}, keyword = {Algorithms,Induced subgraph isomorphism,Subgraph isomorphism,Time complexity,Unique subgraph occurrence}, language = {eng}, month = {06}, pages = {5761}, publisher = {Elsevier}, series = {Information Processing Letters}, title = {Are unique subgraphs not easier to find?}, url = {http://dx.doi.org/10.1016/j.ipl.2018.02.010}, volume = {134}, year = {2018}, }