Are unique subgraphs not easier to find?
(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)
- author
- Kowaluk, Mirosław and Lingas, Andrzej LU
- organization
- publishing date
- 2018-06-01
- 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
- 2022-01-31 02:08:51
@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}},
keywords = {{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}},
doi = {{10.1016/j.ipl.2018.02.010}},
volume = {{134}},
year = {{2018}},
}