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.
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:
- 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
- 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.
- 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).