Maximum Common Subgraph (MCS) is the graph-theoretic problem of finding the largest subgraph that appears (up to isomorphism) as a subgraph of both input graphs simultaneously — identifying the shared structural core between two graphs, with fundamental applications in cheminformatics (finding the common molecular scaffold shared by a drug family), bioinformatics (conserved protein interaction motifs), and software engineering (common code structure detection).

What Is Maximum Common Subgraph?

• Definition: Given two graphs $G_1$ and $G_2$, the Maximum Common Subgraph (MCS) is the largest graph $G_C$ that is isomorphic to a subgraph of both $G_1$ and $G_2$. "Largest" can mean maximum number of nodes (Maximum Common Induced Subgraph — MCIS) or maximum number of edges (Maximum Common Edge Subgraph — MCES). The MCS captures the "structural intersection" — the largest portion of topology shared by both graphs.
• Relationship to GED: The Maximum Common Subgraph is mathematically related to Graph Edit Distance. When edit costs are uniform, $GED(G_1, G_2) = |V_1| + |V_2| - 2|V_{MCS}|$ (for node-based MCS). Finding the MCS is equivalent to finding the minimum-cost graph edit path — they are dual optimization problems, both NP-hard.
• NP-Hardness: The MCS problem is NP-complete — it reduces to the clique problem on the product graph of $G_1$ and $G_2$. The product graph has a node for each compatible node pair $(v_1 in G_1, v_2 in G_2)$ and an edge for each compatible edge pair. The MCS corresponds to the maximum clique in this product graph.

Why Maximum Common Subgraph Matters

• Drug Discovery: Pharmaceutical companies analyze families of bioactive compounds by extracting the MCS — the common molecular scaffold that all active compounds share. This scaffold represents the pharmacophore — the minimal structural requirement for biological activity. Structure-activity relationship (SAR) studies center on identifying this shared core and understanding how modifications affect potency.
• Molecular Similarity Search: MCS-based similarity ($ ext{Tanimoto}_{MCS} = frac{|MCS|}{|G_1| + |G_2| - |MCS|}$) provides a structure-aware similarity metric for database searching. Unlike fingerprint-based methods (which compress molecular structure into fixed-length bit vectors and lose structural detail), MCS preserves the actual shared topology.
• Code Clone Detection: Software engineering uses MCS on program dependency graphs (PDGs) and control flow graphs (CFGs) to detect code plagiarism and refactoring opportunities. Two functions with large common subgraphs in their PDGs likely implement the same algorithm, even if variable names and formatting differ.
• Biological Network Analysis: Comparing protein-protein interaction (PPI) networks across species through MCS reveals conserved functional modules — subnetworks that evolution has preserved because they perform essential biological functions. These conserved modules are prime targets for understanding fundamental cellular processes.

MCS Algorithms

Maximum Common Subgraph is the shared core — extracting the largest structural overlap between two networks to discover the common blueprint that connects different instances of a molecular family, biological pathway, or software architecture.