Maximum common induced subgraph
In graph theory and theoretical computer science, a maximum common induced subgraph of two graphs G and H is a graph that is an induced subgraph of both G and H, and that has as many vertices as possible.
Finding this graph is
Based on
One possible solution for this problem is to build a modular product graph of G and H. In this graph, the largest clique corresponds to a maximum common induced subgraph of G and H. Therefore, algorithms for finding maximum cliques can be used to find the maximum common induced subgraph.[4] Moreover, a modified maximum-clique algorithm can be used to find a maximum common connected subgraph.[5]
The McSplit algorithm (along with its McSplit↓ variant) is a forward checking algorithm that does not use the clique encoding, but uses a compact data structure to keep track of the vertices in graph H to which each vertex in graph G may be mapped. Both versions of the McSplit algorithm outperform the clique encoding for many graph classes.[6] A more efficient implementation of McSplit is McSplitDAL+PR, which combines a Reinforcement Learning agent with some heuristic scores computed with the PageRank algorithm.[7]
Applications
Maximum common induced subgraph algorithms form the basis for both graph differencing and graph alignment. Graph differencing identifies and highlights differences between two graphs by pinpointing changes, additions, or deletions. Graph alignment involves finding correspondences between the vertices and edges of two graphs to identify similar structures.
Maximum common induced subgraph algorithms have a long tradition in bioinformatics, cheminformatics,[8][9] pharmacophore mapping,[10] pattern recognition,[11] computer vision, code analysis, compilers, and model checking.
The problem is also particularly useful in software engineering and model-based systems engineering, where software code and engineering models (e.g., Simulink, UML diagrams) are represented as graph data structures. Graph differencing can be used to detect changes between different versions of software code and models for change auditing, debugging, version control and collaborative team development.
See also
References
- ISBN 0-7167-1045-5A1.4: GT48, pg.202.
- ISBN 978-3-540-55210-9.
- .
- .
- S2CID 215812381
- ISBN 9780999241103
- ISBN 978-989-758-665-1.
- ISSN 1573-7470.
- ISSN 1759-0876.
- S2CID 5202419.
- ISSN 0218-0014.