+1 Recommend
0 collections
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      On the Complexity of Exact Pattern Matching in Graphs: Determinism and Zig-Zag Matching


      , , ,

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.


          Exact pattern matching in labeled graphs is the problem of searching paths of a graph \(G=(V,E)\) that spell the same string as the given pattern \(P[1..m]\). This basic problem can be found at the heart of more complex operations on variation graphs in computational biology, query operations in graph databases, and analysis of heterogeneous networks, where the nodes of some paths must match a sequence of labels or types. In our recent work we described a conditional lower bound stating that the exact pattern matching problem in labeled graphs cannot be solved in less than quadratic time, namely, \(O(|E|^{1 - \epsilon} \, m)\) time or \(O(|E| \, m^{1 - \epsilon})\) time for any constant \(\epsilon>0\), unless the Strong Exponential Time Hypothesis (SETH) is false. The result holds even if node labels and pattern \(P\) are drawn from a binary alphabet, and \(G\) is restricted to undirected graphs of maximum degree three or directed acyclic graphs of maximum sum of indegree and outdegree three. It was left open what happens on undirected graphs of maximum degree two, i.e., when the pattern can have a zig-zag match in a (cyclic) bidirectional string. Also, the reduction created a non-determistic directed acyclic graph, and it was left open if determinism would make the problem easier. In this work, we show through the Orthogonal Vectors hypothesis (OV) that the same conditional lower bound holds even for these restricted cases.

          Related collections

          Most cited references 1

          • Record: found
          • Abstract: not found
          • Conference Proceedings: not found

          Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)


            Author and article information

            10 February 2019


            Custom metadata
            Further developments on our previous work: arXiv:1901.05264
            cs.CC cs.DS

            Data structures & Algorithms, Theoretical computer science


            Comment on this article