Are unique subgraphs not easier to find?

Research output: Contribution to journalArticle

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 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.

Details

Authors
Organisations
External organisations
  • University of Warsaw
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Other Computer and Information Science

Keywords

  • Algorithms, Induced subgraph isomorphism, Subgraph isomorphism, Time complexity, Unique subgraph occurrence
Original languageEnglish
Pages (from-to)57-61
Number of pages5
JournalInformation Processing Letters
Volume134
Publication statusPublished - 2018 Jun 1
Publication categoryResearch
Peer-reviewedYes