# Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms
## 4 Example Analysis  
This section will take the undirected graph in Figure 8(a) as an example to explain the solution process of Q-MeaMetaVC (v\({}_{i}\) is numbered \(i\) in the figure). Figures 10 and 11 show how Q-MeaMetaVC operates in one cycle; the parameters are \(N=1\), \(bms\_v=720\), \(bms\_e=50\), and \(dropCount=76\). The process of Q-MeaMetaVC execution is as follows:  
1 Initially, graph G is in the P membrane, as shown in Figure 9(a). 2 Preprocessing: First, use PreP for pretreatment in the P membrane; because N[v\({}_{28}\)]\(\subseteq\)N[v\({}_{27}\)], v\({}_{27}\) is the dominant vertex. After deleting v\({}_{27}\), v\({}_{29}\) is the dominant vertex, so continue to delete v\({}_{29}\). PreP can no longer reduce G, and the preprocessing stage is over. The result of graph G reduction is shown in Figure 8(b), and the membrane structure at this time is shown in Figure 9(b). 3 The simplified graph of CP and CBP structure is shown in Figure 8(b). The vertices of different connected components belong to different C membranes; v\({}_{1}\)\(\sim\)v\({}_{20}\) and v\({}_{21}\)\(\sim\)v\({}_{26}\), respectively, belong to different connected components (G(V\({}_{1}\)) and G(V\({}_{2}\)) (V\({}_{1}\) = {v\({}_{1}\), v\({}_{2}\), v\({}_{3}\), v\({}_{4}\), v\({}_{5}\), v\({}_{6}\), v\({}_{7}\), v\({}_{8}\), v\({}_{9}\), v\({}_{10}\), v\({}_{11}\), v\({}_{12}\), v\({}_{13}\), v\({}_{14}\), v\({}_{15}\), v\({}_{16}\), v\({}_{17}\), v\({}_{18}\), v\({}_{19}\), v\({}_{20}\)), V\({}_{2}\) = {v\({}_{21}\), v\({}_{22}\), v\({}_{23}\), v\({}_{24}\), v\({}_{25}\), v\({}_{26}\) })), so two C membranes are generated, C\({}_{1}\) and CB\({}_{1}\), responsible for solving the MVC of G(V\({}_{1}\)) and G(V\({}_{2}\)), respectively. In addition, the Answer membrane is generated to store the solved vertex cover, and the Info is passed to Answer. The membrane structure constructed is shown in Figure 9(c). Figure 10: An example of how Q-MeaMetaVC solves a minimum vertex cover problem. Figure 9: An instance of the original graph and its result after preprocessing. 4 Bipartite graph solution stage: After preprocessing, different C membranes are responsible for solving different connected components so that all C membranes will be judged in parallel. In Figure (b)b, G(V\({}_{2}\)) is a bipartite graph, so using Bipartite_graph to obtain its MVC set is {v21, v22, v23}, and it will be transferred to the Answer membrane. Then, the CB\({}_{1}\) membrane lyses itself. The membrane structure after this stage is shown in Figure (d)d.  
5 Sort out the information stage: After the bipartite graph branches are solved, the sum of the vertex of the remaining connected components is counted, and _vNumLeft_ is 20. 6Q-Meta search stage: First, the search time of each C\({}_{i}\) membrane is allocated according to the number of vertices of connected components. The search time of C\({}_{1}\)\(MRT_{1}\) = 3600s. Figure 11: An example about how division and fusion work. (6.1) Construct MP: Since the parameter \(N=1\), ConstructMetaPopulation will construct three M membranes (M\({}_{1}\), M\({}_{2}\), and M\({}_{3}\)) in the C\({}_{1}\) membrane through the GreedyVC+ algorithm: three good membranes (good\({}_{1}\), good\({}_{2}\), good\({}_{3}\)) and the best membrane, where the good\({}_{i}\) membrane is a copy of the M\({}_{i}\), and the best membrane is a copy of the optimal good\({}_{i}\) membrane. The result is shown in Figure 11a. (6.2) Population repair: As shown in Figure 11b, before using the four evolution operators in parallel to search, the repairPopulation algorithm is used to control the number of the M membrane elements. Because \(\mid\) best \(\mid\) = 13, M\({}_{1}\) discards the v\({}_{18}\) with the worst fitness, M\({}_{2}\) discards v\({}_{8}\), and M\({}_{3}\) discards v\({}_{3}\) (all discarded vertices are marked in orange). Finally, the number of vertices for all M membranes is 12 (\(\mid\) best \(\mid\) -1).