# Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms
## 1 Introduction  
The rapid development of the internet and the advancement of information technology have produced a large amount of large-scale graph data, such as complex and large-scale social networks [1], sensor networks [2], etc. In the real world, the MVC algorithm is widely used--for example, to solve the sensor placement problem in sensor networks. In a logistics park, monitoring each road vehicle is achieved by arranging the fewest number of sensors. Each road intersection is represented by a vertex in the graph, and each road is represented by an edge in the graph. In this way, the sensor placement problem is transformed into the problem of finding the MVC in the abstract formed graph. Another example is key individual issues in social networks. In a group, collaboration between individuals (such as co-publishing papers) is a common occurrence. We hope to find the fewest number of individuals in the group, through which we can obtain collaborative relationships between all individuals. Each individual is represented with a vertex in the graph. When there is a collaboration between individuals \(a\) and \(b\), an edge is added between their corresponding vertices. This way, the key individual problem is transformed into the MVC in the graph. Therefore, finding the MVC on these large graphs has attracted the attention of many researchers. With the efforts of researchers, there are already many MVC solutions that show good performance in terms of operating efficiency and the accuracy of the obtained solutions. In the research of vertex cover solvers for large-scale graphs, local search algorithms have received more and more attention [3; 4; 5; 6; 7]. The authors of [3] proposed a simple and fastedge-weighting method called Edge Age-Based Best from Multiple Selections (EABMS), which selects edges by using edge-weighting heuristics in the local search field and its time complexity O(1E1). Based on EABMS, a large-scale graph-oriented MVC solving framework EAVC was proposed. Comparing the results of the EAVC solver with existing solvers shows that EABMS is effective. The authors of [4] proposed a method based on the combination of the rough set theory and random local search algorithm, using the reduction method to simplify and reduce the complexity quickly. The (p, q)-reverse incremental verification mechanism is also used, applying incremental positive region update techniques to verify whether the desired attribute pair can be found quickly; the primary purpose of these rules is to avoid double calculations and jumping out of local optima. The authors of [5] studied the random search heuristic behavior of the MVC in sparse random graphs based on the G(n, c/n) model in order to strictly prove that the improved Karp-Sipser algorithm, called KS-VC, can be used to solve the optimality problem of c \(<\) e. At the same time, an iterative local search algorithm called Iterated Local Search (ILS) was defined. It combines randomized local search in neighborhoods of size 2 with a greedy local search algorithm. For c \(<\) 1, it reproduces the decision of KS-VC with good probability in polynomial time. The authors of [6] proposed a new method to extend the local search algorithm for large graphs. The approach builds on the theoretical assumption that large graphs consist of distinct substructures that are relatively easy to optimize. It is based on parallel kernelization and reduces the given graph by making u parallel randomized runs of the given local search and fixing components that have been chosen in all u runs. Additional runs of the local search method process the resulting instances. Experiments show that the proposed parallel kernelization technique can reduce standard benchmarks and large real-world graphs to 10-20% of their initial size. FastWVC [7] is designed to solve the minimum weight vertex cover (MWVC) problem in a massive graph, and a construction process is proposed to generate high-quality initial vertex cover in a short time.