Maximum Common Subgraph Task

From GM-RKB
Jump to navigation Jump to search

A Maximum Common Subgraph (MCS) Task is a graph matching task that can be solved by a MCS system by implementing a MCS Algorithm.



References

2018

2009

  • (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem
    • In complexity theory, maximum common subgraph-isomorphism (MCS) is an optimization problem that is known to be NP-hard. The formal description of the problem is as follows:
      • Maximum common subgraph-isomorphism(G1, G2)
      • Input: Two graphs G1 and G2.
      • Question: What is the largest induced subgraph of G1 isomorphic to a subgraph of G2?
    • The associated decision problem, i.e., given G1, G2 and an integer [math]\displaystyle{ k }[/math], deciding whether G1 contains a subgraph of at least k edges isomorphic to a subgraph of G2 is NP-complete.
    • One possible solution for this problem is to build a modular product graph, in which the largest clique represents a solution for the MCS problem.
    • MCS algorithms have a long tradition in cheminformatics and pharmacophore mapping.

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.

2004

2003

2002a

2002b

1998

1997

1992

1981