Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a directed acyclic graph G and a path made up from its set of nodes N, what is the closest approximate match to N, 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:


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.


Edit: I ended up using a dynamic programming algorithm, independently also suggested in the accepted answer. Good call! It is probably the most accurate option as well, and barely more "complex" than the string-to-string case when the average # of edges per node is low.

share|improve this question

closed as off-topic by Andres Caicedo, Ryan Budney, David White, Andrey Rekalo, Chris Godsil Jul 22 '13 at 11:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Andres Caicedo, Ryan Budney, David White, Andrey Rekalo, Chris Godsil
If this question can be reworded to fit the rules in the help center, please edit the question.

for q1, I'm not seeing the problem. given the sequence of nodes in the path, why can't you just verify that directed edges exist between each adjacent pair of nodes ? –  Suresh Venkat May 27 '10 at 1:09
good point, I guess q2 is what I'd like know more about. –  Deniz May 27 '10 at 3:53
add comment

1 Answer 1

up vote 1 down vote accepted

If graph is acyclic you can use some sort of dynamic programming. Let $a_{u,k}$ be the best distance you can get if you start from vertex $u \in G$ and consider only $k$ last vertices of your given path.

It's quite straightforward how to calculate all $a_{u,k}$ based on all values of $a_{u',k'}$ with $u'$ "after" $u$ and $k' < k$: you just iterate over all edges going from vertex $u$.

This approach works in $O(|G| \times strlen)$ time.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.