Advanced

Are unique subgraphs not easier to find?

Kowaluk, Mirosław and Lingas, Andrzej LU (2018) In Information Processing Letters 134. p.57-61
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˜(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... (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˜(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.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
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
0020-0190
DOI
10.1016/j.ipl.2018.02.010
language
English
LU publication?
yes
id
1fede768-d095-4c89-b7ae-8c84e13b2682
date added to LUP
2018-03-05 07:55:39
date last changed
2018-05-29 11:12:28
@article{1fede768-d095-4c89-b7ae-8c84e13b2682,
  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         = {0020-0190},
  keyword      = {Algorithms,Induced subgraph isomorphism,Subgraph isomorphism,Time complexity,Unique subgraph occurrence},
  language     = {eng},
  month        = {06},
  pages        = {57--61},
  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},
}