On the complexity of approximately matching a string to a directed graph