Maximum Common Subgraph

From GM-RKB
(Redirected from maximum common subgraph)
Jump to navigation Jump to search

A Maximum Common Subgraph (MCS) is a graph that is subgraph of two graphs and that has many vertices as possible.



References

2018a

2018b

2007

Inputs: A pair of graphs, [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math], and a positive integer [math]\displaystyle{ k }[/math].
Question: Do [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math] have a common subgraph of order [math]\displaystyle{ k }[/math] or more?
MCS finds application in many domains. It has been used in bioinformatics 15, chemistry [9, 10], pattern recognition [3, 8], and a variety of other areas. Unfortunately, MCS is an exceedingly difficult problem, with several well-known NP-complete problems reducing to it. The maximum clique problem, for example, corresponds to the special case in which [math]\displaystyle{ |G_1| = |G_2| }[/math] and [math]\displaystyle{ G_1 }[/math] is complete.

2002a

2002b