SymSplit · PACMMOD Vol. 4 No. 3 · SIGMOD 2026
Exact maximum common induced subgraph (MCIS) computation via dual symmetry breaking — exploiting both variable and value graph symmetries to drastically prune the branch-and-bound search space.
The maximum common subgraph (MCS) problem asks: given two graphs G and H, what is the largest graph that appears as a subgraph of both? The size of the maximum common subgraph is a natural measure of how structurally similar two graphs are, which is why MCS is used for molecule comparison, graph similarity search, and graph matching.
There are two standard variants. The maximum common induced subgraph (MCIS) maximises the number of matched vertices, and every edge between matched vertices in one graph must also exist in the other. The maximum common edge subgraph (MCES) instead maximises the number of shared edges. Both are NP-hard, so exact solvers rely on carefully pruned search.
mcsolver solves the induced variant exactly with SymSplit, a branch-and-bound algorithm in the McSplit family that detects symmetries in both input graphs and skips search branches that can only produce equivalent solutions.
The maximum common (induced) subgraph problem underlies structural similarity in a broad range of domains. Below are the primary application areas.
Finding the largest shared substructure of two molecules for similarity search, scaffold analysis and reaction mapping.
Comparing protein structures, interaction networks and metabolic pathways to find conserved functional modules.
Matching graph-based representations of images, shapes and scenes when exact isomorphism is too strict.
Measuring similarity between social, communication or knowledge graphs and aligning their common structure.
Identifying common sub-circuits between designs for equivalence checking and IP reuse detection.
Comparing control-flow and call graphs to detect code clones, plagiarism and malware variants.
SymSplit extends the McSplit branch-and-bound framework with dual symmetry breaking: it detects modular symmetries based on local neighbourhood hashes in both the variable graph G and the value graph H, then prunes isomorphic subtrees during search. Variable symmetry (previously exploited by RRSplit) and value symmetry (novel contribution) are composed without violating completeness.
Symmetry detection runs in O(n²) via Boost hash-based neighbourhood grouping. The resulting symmetry classes enable O(1) pruning lookups during BnB traversal.
| Method | Var. Sym. | Val. Sym. | Exact |
|---|---|---|---|
| McSplit | ✗ | ✗ | ✓ |
| RRSplit | ✓ | ✗ | ✓ |
| Trummer | ✓ | ✓ | ✗ |
| SymSplit | ✓ | ✓ | ✓ |
SymSplit achieves an average 75.7× speedup over RRSplit and solves more instances within any fixed branch count — with the strongest gains on high-symmetry graph datasets (BI, LV).
Upload two graphs in edge-list format or paste them directly. The SymSplit backend will return the exact Maximum Common Induced Subgraph with vertex mapping.
Click or drag a graph file
Edge list · one edge per line
Click or drag a graph file
Edge list · one edge per line
Upload or paste two graphs then click Run
Given two graphs G and H, the maximum common subgraph (MCS) problem asks for the largest graph that is isomorphic to a subgraph of both G and H. It is a fundamental measure of structural similarity between graphs and is NP-hard.
The maximum common induced subgraph (MCIS) maximises the number of vertices and requires that all edges among the chosen vertices are preserved in both graphs. The maximum common edge subgraph (MCES) maximises the number of shared edges and does not require the subgraphs to be induced.
State-of-the-art exact solvers use branch-and-bound search, notably McSplit, its symmetry-aware extension RRSplit, and SymSplit, which adds value-graph symmetry breaking and is more faster than RRSplit.