Description

What is the amount of overlap between two given graphs? This is a very hard question in general (finding the maximum common subgraph of two graphs is NP-complete) which, at the same time, crops up in many situations. Examples applications are: diagram versioning (where an algorithm comparable to "diff" for text files is necessary to avoid storing entire diagrams) or incremental graph matching (where an attempt is made to find matches for many similar graphs). A related question is that of the edit distance of graphs: how much do you (at least) have to modify one graph, in terms of additions and deletions, to turn it into another?

The eventual objective of this assignment is to come up with an implementation that is actually able to produce common subgraphs, which should approximate the optimal solution as well as possible given the complexity of the problem. In order to fit into existing software, the implementation should be done in Java.

Tasks

• Get a good overview of the (maximum) common subgraph problem
• Investigate existing solution approaches
• Implement an algorithm to produce common subgraphs

Requirements

• Affinity with graph theory and algorithms
• Good programming skills

Additional Resources

1. The paper