  We study the problem of matching a string in a labeled graph. Previous
research has shown that unless the Orthogonal Vectors Hypothesis (OVH) is
false, one cannot solve this problem in strongly sub-quadratic time, nor index
the graph in polynomial time to answer queries efficiently (Equi et al. ICALP
2019, SOFSEM 2021). These conditional lower-bounds cover even deterministic
graphs with binary alphabet, but there naturally exist also graph classes that
are easy to index: E.g. Wheeler graphs (Gagie et al. Theor. Comp. Sci. 2017)
cover graphs admitting a Burrows-Wheeler transform -based indexing scheme.
However, it is NP-complete to recognize if a graph is a Wheeler graph (Gibney,
Thankachan, ESA 2019).
  We propose an approach to alleviate the construction bottleneck of Wheeler
graphs. Rather than starting from an arbitrary graph, we study graphs induced
from multiple sequence alignments (MSAs). Elastic degenerate strings (Bernadini
et al. SPIRE 2017, ICALP 2019) can be seen as such graphs, and we introduce
here their generalization: elastic founder graphs. We first prove that even
such induced graphs are hard to index under OVH. Then we introduce two
subclasses, repeat-free and semi-repeat-free graphs, that are easy to index. We
give a linear time algorithm to construct a repeat-free non-elastic founder
graph from a gapless MSA, and (parameterized) near-linear time algorithms to
construct semi-repeat-free (repeat-free, respectively) elastic founder graphs
from general MSAs. Finally, we show that repeat-free elastic founder graphs
admit a reduction to Wheeler graphs in polynomial time.
