Advanced

Unique subgraphs are not easier to find

Kowaluk, Miroslaw ; Lingas, Andrzej LU and Lundell, Eva-Marta LU (2013) In International Journal of Computer Mathematics 90(6). p.1247-1253
Abstract
Given a pattern graph H with l edges, and a host graph G guaranteed to contain at most one occurrence of a subgraph isomorphic to H, we show that the time complexity of the problem of finding such an occurrence (if any) in G as well as that of the decision version of the problem are within a multiplicative factor O(l) of the time complexity for the corresponding problem in the general case, when G may contain several occurrences of H. It follows that for pattern graphs of constant size, the aforementioned uniqueness guarantee cannot yield any asymptotic speed up. We also derive analogous results with the analogous multiplicative factor linear in the number of vertices of H in the induced case when occurrences of induced subgraphs of G... (More)
Given a pattern graph H with l edges, and a host graph G guaranteed to contain at most one occurrence of a subgraph isomorphic to H, we show that the time complexity of the problem of finding such an occurrence (if any) in G as well as that of the decision version of the problem are within a multiplicative factor O(l) of the time complexity for the corresponding problem in the general case, when G may contain several occurrences of H. It follows that for pattern graphs of constant size, the aforementioned uniqueness guarantee cannot yield any asymptotic speed up. We also derive analogous results with the analogous multiplicative factor linear in the number of vertices of H in the induced case when occurrences of induced subgraphs of G 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
time complexity, induced subgraph isomorphism, isomorphism, unique subgraph occurrence, graph algorithms, subgraph
in
International Journal of Computer Mathematics
volume
90
issue
6
pages
1247 - 1253
publisher
Taylor & Francis
external identifiers
  • wos:000320649100007
  • scopus:84879519680
ISSN
1029-0265
DOI
10.1080/00207160.2012.701287
language
English
LU publication?
yes
id
d9133a6a-a3d4-4b48-95f7-8968995b1957 (old id 3983199)
date added to LUP
2016-04-01 10:52:29
date last changed
2020-01-12 06:01:00
@article{d9133a6a-a3d4-4b48-95f7-8968995b1957,
  abstract     = {Given a pattern graph H with l edges, and a host graph G guaranteed to contain at most one occurrence of a subgraph isomorphic to H, we show that the time complexity of the problem of finding such an occurrence (if any) in G as well as that of the decision version of the problem are within a multiplicative factor O(l) of the time complexity for the corresponding problem in the general case, when G may contain several occurrences of H. It follows that for pattern graphs of constant size, the aforementioned uniqueness guarantee cannot yield any asymptotic speed up. We also derive analogous results with the analogous multiplicative factor linear in the number of vertices of H in the induced case when occurrences of induced subgraphs of G isomorphic to H are sought.},
  author       = {Kowaluk, Miroslaw and Lingas, Andrzej and Lundell, Eva-Marta},
  issn         = {1029-0265},
  language     = {eng},
  number       = {6},
  pages        = {1247--1253},
  publisher    = {Taylor & Francis},
  series       = {International Journal of Computer Mathematics},
  title        = {Unique subgraphs are not easier to find},
  url          = {http://dx.doi.org/10.1080/00207160.2012.701287},
  doi          = {10.1080/00207160.2012.701287},
  volume       = {90},
  year         = {2013},
}