Algorithm - compute the longest common subsequence (LCS) of two DAGs

Question

I have two directed acyclic graph and I need to compute the longest common subsequence (LCS) of these graphs. For two strings/subsequences I use LCS algorithm using dynamic programming (DP) but how can I modify this algorithm to the graphs?

Any idea?

whole task:

Let G is a directed acyclic graph in which each vertex is labeled with a symbol from a finite alphabet. Different vertices may be marked with the same symbol. Each directed path in G has trace formed by concatenating the symbol of vertices from the path. Sequence of graph G is a subsequence of trace of some directed path in G.

Design an efficient algorithm that computes the longest common sequence of two given directed acyclic graph.

Example: strings DYNAMIC, PROGRAM and DEPTHFIRST are sequences of oriented acyclic graph of the picture. String PROGRAM is its trace.

enter image description here

You fail to demonstrate any kind of research effort. Also this seems to be a repost of another question that has been deleted by now — Niklas B.
I try to search information, excercies,... but I don´t know how to modify the LCS algorithm. So some hint would be helpful, not this comments... — Pepa Zapletal
Think about the implicit graph of node pairs (x, y) with x being a node from the first DAG and y from the second. add edges (A(x), y), (x, A(y)) and (A(x), A(y)) where A is your adjacency lists. Assign edge weights so that a longest path in this graph corresponds to the LCS, like in the case of strings. Then solve the longest path problem. — Niklas B.

Antti Huima Antti Huima · Accepted Answer · 2014-05-12T10:22:36

Let A be the first DAG and B the second DAG. For any two nodes a in A and b in B having, define the length of the longest common subsequence that starts from a in A and from b in B to be

LCS(a,b) =  0 + max LCS(a',b') for any pair (a',b') s.t. a->a' and b->b'
                               or a=a' and b->b', or b=b' and a->a'
                               if a and b do NOT share same label

            1 + max LCS(a',b') for any pair (a',b')
                               s.t. a -> a' and b -> b'
                               if a and b DO share same label

Then apply dynamic programming over |A| x |B| pairs (a, b) and read the value for the pairs that pertain to DAG sources ("start nodes").

Algorithm - compute the longest common subsequence (LCS) of two DAGs

1 Answers