Graphs are important data structures that can be used to model many real-world problems. One of the most basic graph problems is to measure the similarity of graphs.
Given two graphs \(G_0\)  and \(G_1\) , the Maximum Common induced Subgraph (MCS) aims to find an induced subgraph \(G_0^{\prime }\)  in \(G_0\)  and an induced subgraph \(G_1^{\prime }\)  in \(G_1\)  such that \(G_0^{\prime }\)  and \(G_1^{\prime }\)  are isomorphic and the number of vertices of \(G_0^{\prime }\)  and \(G_1^{\prime }\)  is maximized. The vertices of \(G_0^{\prime }\)  are said to be matched with the vertices of \(G_1^{\prime }\) . MCS has a variant called the Maximum Common Connected induced Subgraph (MCCS), which further requires the induced subgraph to be connected.
These problems are widely applied in various domains, such as biochemistry [1]}, [2]}, cheminformatics [3]}, [4]}, [5]}, compilers [6]}, model checking [7]}, molecular science [8]}, pattern recognition [9]}, malware detection [10]}, [11]}, video and image analysis [12]}, [13]}, [14]}, etc.
