# Matching a set of paths to an incrementally generated graph

I am working on an approximate matching problem, where I have a set of paths in an unknown graph (A) and a partial graph (B), where B is generated incrementally during the matching process (and can be potentially infinite).

The problem is to match the maximum number of edges in the paths to the smallest graph B. The matching should be such that the order in which the edges appear in the paths is preserved in the graph, and each path is matched to a distinct path in the graph. This distinctness requirement comes from the fact that each path in graph A must have a corresponding path in graph B but might not generated yet.

The graph nodes are immaterial and the edges have non-unique labels upon which matching is performed. Also, the paths to be matched can have arbitrary edges added/deleted while matching is to the graph B. If the solution does not meet a threshold (X% of edges matched), we can query an oracle, that generates a slightly bigger (i.e., more complete) graph but the goal is to minimize the queries as the graph can potentially be infinite.

Example:

Paths:
-A-> -B-> -C->
-A-> -D->

Graph:
-A-> -X-> -B-> -C->

Result:
Matched: A-A, B-B, C-C
Unmatched: D

Query Oracle (A-D?) gives resulting graph.
-A-> -X-> -B-> -C->
|-D->

Result:
Matched: A-A, B-B, C-C, D-D

I tried to lookup standard solutions from assignment and graph isomorphism but didn’t find anything similar. So, here is a solution I came up with:

1. I am using a branch and bound algorithm to match every edge in the paths to every edge in the graph (M X N table). For each possible assignment, I am keeping track of which other assignments are possible containing with the particular assignment
2. The bounding condition (& feasibility) is defined by the same ordering of the edges in the graph as it is in the paths. Also, two paths cannot be mapped such that they violate each others ordering.
3. If we are not happy with this solution, we can query the oracle, get a bigger graph and repeat 1 & 2. Otherwise, the technique outputs the possible edge mappings.

My question is that I am not sure if my solution still falls under branch & bound algorithms, as it no longer follows the standard branch & bound tree structure. Also, it would be great if anyone can point out optimizations or a better way to do this.

Note: At every iteration, N changes and the table grows horizontally. The biggest inefficiency is in step #2, which needs to be recomputed at every stage for safety (e.g., a loop being added in the graph invalidates previous solutions).

• Welcome to CS.SE! The algorithmic problem is not well-defined, as stated. Please edit the question to clarify what you are looking to solve. 1. Are you looking for any matching, or for an optimal matching? If you want an optimal matching, what is your objective function (your metric of optimality)? In other words, how do you define which of the many possible matches are optimal? If you are just looking for any matching, what's wrong with a matching that just says "delete all the edges from the path, now it matches, woo-hoo!"? – D.W. Mar 29 '15 at 20:13
• 2. What are the ordering constraints? What does "violate each others ordering" mean? Can you give a precise, mathematical specification? 3. What is the relevance of the fact that B is growing or the oracle or any of that? It seems like this problem can be posed about a single, static set of paths from A and a single, static graph B. It might be worth trying to get to the core/essence of your problem, and avoiding distracting details (you can always ask another question about how to deal with the dynamic aspects). – D.W. Mar 29 '15 at 20:14
• Thanks @D.W.! The ordering is the order in which the edges appear in the paths and graphs. I'm looking for an optimal matching in the static graph and if not able to find one, then a list of questions to ask to the oracle.. – shauvik Mar 29 '15 at 20:47
• OK. In that case, what do you mean by an optimal matching? What is your objective function? What is your definition of which matching counts as optimal? Is it "matches the largest total number of edges from the paths of A that were provided in the input"? (So deletions and insertions cost nothing; all that matters is counting the number of edges that do match?) – D.W. Mar 29 '15 at 22:42
• Hi @D.W., Thank you so much for following up on this problem. Optimal matching is one which maximizes the edge matching from all paths (from graph A) onto distinct paths in graph B. The problem with considering paths individually is that it doesn't ensure distinctness. More than one paths (in A) can be matched to one path inside graph B. Also, there might be more than one optimal solutions for a path, and in this case, distinctiveness of the matching paths can help select the solution. I really like your dynamic programming based solution but perhaps it can't generate all optimal solutions.. – shauvik Mar 30 '15 at 5:43

I'll outline a solution to your problem. There are two key insights: (1) each path can be analyzed independently of all the others; (2) the best match can be computed using dynamic programming. I'll start with a simpler version of your problem and build up to a solution for the full problem.

## Finding the best match for a single path

Suppose we have a single path (from graph A) and we want to find its best match in graph B. This can be solved with dynamic programming.

Let $P$ denote the path from graph A, and $P_k$ denote the prefix of the graph containing its first $k$ edges. If $v$ is a vertex in $B$ and $k$ is a natural number, define $f(k,v)$ to be the number of edges present in the optimal match of $P_k$ inside graph B, such that the match ends at vertex $v$. Then $f(k,v)$ follow the following recursive relation:

$$f(k+1,w) = \max(\max \{f(j,v) : v \to^* w,j \le k \}, 1 + \max \{ f(j,v) : v \to^* v' \to w, j \le k\})$$

where the former max is taken over all $v$ such that $w$ is reachable from $v$ in B, and latter max is taken over all $v,v'$ such that $v'$ is reachable from $v$ in B and there is an edge from $v'$ to $w$ in B whose label is the same as the label on the $k$th edge of $P$. Also, we have the base case $f(0,v) = 0$ for all $v$. Finally, notice that the number of edges matched in the optimal match for $P$ is given by $\max\{f(k,v) : v \in V\}$.

This recursive relation immediately gives us a dynamic programming algorithm to compute the number of edges matched in the optimal match for $P$. You can also augment the algorithm to retrieve the match itself, if desired.

The running time is polynomial. Suppose the path has length $\ell$ and graph B has $n$ vertices and $m$ edges. Then there are $O(\ell n)$ subproblems, and each subproblem takes $O(m \el)$ time to solve (on average), so the running time is $O(nm \ell^2)$. [It might be possible to further improve the running time by decomposing B into strongly connected components and only computing $f(k,v)$ values for one vertex $v$ in each strongly connected component, but I haven't tried to optimize this algorithm.]

Note that this gives the exact optimum, not an approximation. It's not a heuristic -- it always gives the optimal solution.

If you don't find the dynamic programming algorithm intuitive, here is another perspective. You can think of this from an automata theory perspective. Suppose the path has edge labels $e_1,\dots,e_{\ell}$. Let $M$ be the automaton that accepts every subsequence of regexp $\Sigma^* e_1 \Sigma^* e_2 \Sigma^* \cdots \Sigma^* e_{\ell} \Sigma^*$ (this is a regular language, so it has a NFA, call it $M$). Form the parallel composition of $M$ and B, using the product construction; call it $M'$. Now look for the longest path in $M'$. This is exactly the optimal match you are looking for.

## Finding the best match for a collection of paths

Now suppose we have multiple paths and want to match them all to B. Well, it turns out that the optimal way to match a collection of paths is to consider each path separately, finding the optimal match for that path in isolation (independent of all the other pairs), and then combine these matches.

So if we have $q$ paths, we can just invoke the algorithm above $q$ times, once for each path. The running time will be $O(nm \ell^2 q)$.

## Dealing with changes to B

In your problem, each time you find the best matches for a collection of paths, you then update B to get a new graph. This can be easily handled by simply running the algorithm from scratch again on the new graph. In each round, you run the $O(nm \ell^2 q)$-time algorithm from above on the current graph B. Then, you use whatever technique you have in mind for growing the graph B, and start over again. This doesn't let you re-use work from previous rounds, but it's a very simple technique, and it computes the optimal solution.