1) Given a directed acyclic graph `G` and a path made up from its set of nodes `N`,  how can we determine if this (directed) path exists in `G`?  
2) If there is no exact match, what is the closest approximate match, equipped with an intuitive notion of distance?

A path in a directed acyclic graph is essentially a string (that uses the set of nodes as the alphabet), so when comparing paths one can make use of edit distances developed for approximate string matching:

There are many algorithms for approximate string matching:

http://en.wikipedia.org/wiki/Approximate_string_matching

This string matching answers the question when the `G` itself is also a path.. then we're merely asking to compare two strings. 

Asking if an arbitrary graph `A` built from the same set of nodes is a sub-graph of `G` is the general case of the problem, but I'm only interested in the case where `A` is a path and `G` is directed & acyclic.

Any general pointers are also welcome.