# Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms
## 3 A MVC Solver Based on MEA--Q-MaeMetaVC
### Bipartite Graph Solving Algorithm
#### 3.3.1 Create a Membrane Structure
This graph only has one connected component, so \(j\) = 1. First, construct the X, Y, MaxM, and best membranes in the CB\({}_{1}\) membrane, as shown in Figure 7(a). Then, place the two independent sets {V\({}_{1}\), V\({}_{2}\), V\({}_{3}\)} and {V\({}_{4}\), V\({}_{5}\), V\({}_{6}\), V\({}_{7}\)} into the CB\({}_{1}\).X and CB\({}_{1}\).Y membranes, respectively. At the same time, use the _Hungarian_ algorithm to find a maximum matching {(V\({}_{1}\), V\({}_{4}\)), (V\({}_{2}\), V\({}_{5}\)), (V\({}_{3}\), V\({}_{7}\))} in Figure 7, and put its vertex set intothe MaxM membrane. The number of vertices in MaxM is 6, so the value of _max_ is equal to 3. Separate the unmatched vertex V\({}_{6}\) from the CB\({}_{1}\).Y membrane and put it into the CB\({}_{1}\).Y' membrane. While CB\({}_{1}\).X' is empty, lyse it, as shown in Figure 7(b). Separate the neighborhood V\({}_{1}\) of V\({}_{6}\) from the CB\({}_{1}\).X membrane and put it into the CB\({}_{1}\).best membrane; the vertex must be included in the MVC set. At the same time, take the neighbors V\({}_{4}\) and V\({}_{6}\) of V\(1\) as unmatched vertices, separate them from CB\({}_{1}\).Y, and update CB\({}_{1}\).Y', as shown in Figure 7(c). In the same manner, separate their neighbors V\({}_{1}\) and V\({}_{2}\) from the CB\({}_{1}\).X membrane and put them into the CB\({}_{1}\).best membrane, as shown in Figure 7(c). Figure 7(d) is the final result. The MVC set of the bipartite graph is {V\({}_{1}\), V\({}_{2}\), V\({}_{3}\)}. ### Non-Bipartite Graph Solution Algorithm

This section mainly explains the solution of non-bipartite graphs, including the design of the initialization algorithm, repair operator, division and fusion operator, selection, and cytolysis operator. #### 3.4.1 Initialization Algorithm

The initialization algorithm's quality significantly impacts the quality of the solution to the MVC, especially when solving larger instances. Before initialization, the membrane structure needs to be created first, which is performed by the non-bipartite graph, as shown in Algorithm 5. Figure 8: Bipartite graph solution example. Figure 7: The original bipartite graph. #### 3.4.2 Repair Operator Implementation

The significance of the repair operator is to ensure that the membranes in the population maintain certain characteristics. Q-MeaMetaVC ensures that the number of elements per membrane is one less than the size of the smallest vertex cover currently found to ensure convergence. For each iteration of the C membrane, Q-MeaMetaVC will use the optimal search results to update the optimal population solution C.best membrane (Algorithm 2, lines 19-20) and then repair the entire population (Algorithm 2, line 25) so that the number of elements in all M membranes is 1 C.best 1-1 (Algorithm 7, lines 1-2), and the same is actual in the process of cytolysis and selection (Algorithm 13, Line 7). ```
Input: \(i\), population size \(NP\); Output: C\({}_{i}\) membrane;
1 C\({}_{i}\).MP = [M\({}_{1}\),M\({}_{2}\),...,M\({}_{NP}\)];
2 C\({}_{i}\).GOODP = [good\({}_{1}\),good\({}_{2}\),...,good\({}_{NP}\)];
3 x+-1;
4 for x\(\leq\) NP do
5 M\({}_{x}\) = GreedyVC+(G(V\({}_{i}\)));
6 good\({}_{x}\) = M\({}_{x}\);
7 end for
8 C\({}_{i}\).best = the optimal M membrane in MP;
9 return C\({}_{i}\) membrane;
```
**Algorithm 6**ConstructMetaPopulations //Population initialization algorithm

Algorithm 8 is the process of repairing a single membrane. Because of the greedy strategy adopted, the complexity is high, so after updating the optimal solution (Algorithm 9, line 4) and selecting the solution (Algorithm 13, line 7). Every time add the highest fitness vertex(lines 6-7) or remove the lowest fitness vertex (lines 2-3) so that the number of elements in the M membrane reaches the target value. To avoid circular searching,elements with an age of 0 (whose state has just changed during the current iteration) will not be selected.