  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.
