  The CNF formula satisfiability problem (CNF-SAT) has been reduced to many
fundamental problems in P to prove tight lower bounds under the Strong
Exponential Time Hypothesis (SETH). Recently, the works of Abboud, Hansen,
Vassilevska W. and Williams (STOC 16), and later, Abboud and Bringmann (ICALP
18) have proposed basing lower bounds on the hardness of general boolean
formula satisfiability (Formula-SAT). Reductions from Formula-SAT have two
advantages over the usual reductions from CNF-SAT: (1) conjectures on the
hardness of Formula-SAT are arguably much more plausible than those of CNF-SAT,
and (2) these reductions give consequences even for logarithmic improvements in
a problems upper bounds.
  Here we give tight reductions from Formula-SAT to two more problems: pattern
matching on labeled graphs (PMLG) and subtree isomorphism. Previous reductions
from Formula-SAT were to sequence alignment problems such as Edit Distance,
LCS, and Frechet Distance and required some technical work. This paper uses
ideas similar to those used previously, but in a decidedly simpler setting,
helping to illustrate the most salient features of the underlying techniques.
