A New Approach Based on Centrality Value in Solving the Minimum Vertex Cover Problem: Malatya Centrality Algorithm

Abstract

The graph is a data structures and models that used to describe many real-world problems. Many engineering problems, such as safety and transportation, have a graph-like structure and are based on a similar model. Therefore, these problems can be solved using similar methods to the graph data model. Vertex cover problem that is used in modeling many problems is one of the important NP-complete problems in graph theory. Vertex-cover realization by using minimum number of vertex is called Minimum Vertex Cover Problem (MVCP). Since MVCP is an optimization problem, many algorithms and approaches have been proposed to solve this problem. In this article, Malatya algorithm, which offers an effective solution for the vertex-cover problem, is proposed. Malatya algorithm offers a polynomial approach to the vertex cover problem. In the proposed approach, MVCP consists of two steps, calculating the Malatya centrality value and selecting the covering nodes. In the first step, Malatya centrality values are calculated for the nodes in the graph. These values are calculated using Malatya algorithm. Malatya centrality value of each node in the graph consists of the sum of the ratios of the degree of the node to the degrees of the adjacent nodes. The second step is a node selection problem for the vertex cover. The node with the maximum Malatya centrality value is selected from the nodes in the graph and added to the solution set. Then this node and its coincident edges are removed from the graph. Malatya centrality values are calculated again for the new graph, and the node with the maximum Malatya centrality value is selected from these values, and the coincident edges to this node are removed from the graph. This process is continued until all the edges in the graph are covered. It is shown on the sample graph that the proposed Malatya algorithm provides an effective solution for MVCP. Successful test results and analyzes show the effectiveness of Malatya algorithm.

Keywords

• Minimum vertex cover
• Centrality algorithm.
• Graph theory
• Malatya centrality algorithm

References

1. Akram, VK, & Ugurlu, O. (2022). A localized distributed algorithm for vertex cover problem. Journal of Computational Science , 58(May 2021), 101518. Retrieved from https://doi.org/10.1016/j.jocs.2021.101518
2. Borgatti, SP (2005). Centrality and network flow. Social Networks , 27(1), 55–71. Retrieved from https://doi.org/10.1016/j.socnet.2004.11.008
3. Dagdeviren, ZA (2021). Weighted Connected Vertex Cover Based Energy-Efficient Link Monitoring for Wireless Sensor Networks Towards Secure Internet of Things. IEEE Access , 9, 10107–10119. Retrieved from https://doi.org/10.1109/ACCESS.2021.3050930
4. Dinur, I., & Safra, S. (2005). On the hardness of approximating vertex cover. Annals of Mathematics , 162(1), 439–485. Retrieved from https://doi.org/10.4007/annals.2005.162.439
5. Gusev, V.V. (2020). The vertex cover game: Application to transport networks. Omega , 97, 102102. Retrieved from https://doi.org/10.1016/j.omega.2019.08.09
6. Hossain, A., Lopez, E., Halper, SM, Cetnar, DP, Chief, AC, Strickland, D., … Salis, HM (2020). Automated design of thousands of nonrepetitive parts for engineering stable genetic systems. Nature Biotechnology , 38(12), 1466–1475. Retrieved from https://doi.org/10.1038/s41587-020-0584-2
7. Jovanovic, R., Sanfilippo, AP, & Voß, S. (2022). Fixed set search applied to the multi-objective minimum weighted vertex cover problem. Journal of Heuristics , 28(4), 481–508. Retrieved from https://doi.org/10.1007/s10732-022-09499-z
8. Khattab, H., Mahafzah, BA, & Sharieh, A. (2022). A hybrid algorithm based on modified chemical reaction optimization and best-first search algorithm for solving minimum vertex cover problem. Neural Computing and Applications , 34(18), 15513–15541. Retrieved from https://doi.org/10.1007/s00521-022-07262-w

9. Kumar, G., Duhan, N., & Sharma, AK (2011). Page ranking based on number of visits of links of Web page. In 2011 2nd International Conference on Computer and Communication Technology (ICCCT-2011) (pp. 11–14). IEEE. Retrieved from https://doi.org/10.1109/ICCCT.2011.6075206
10. Yigit, Y., Dagdeviren, O., & Challenger, M. (2022). Self-Stabilizing Capacitated Vertex Cover Algorithms for Internet-of-Things-Enabled Wireless Sensor Networks. Sensors , 22(10), 3774. Retrieved from https://doi.org/10.3390/s22103774
11. Zhang, YJ, Mu, XD, Liu, XW, Wang, XY, Zhang, X., Li, K., … Dong, C. (2022). Applying the quantum approximate optimization algorithm to the minimum vertex cover problem. Applied Soft Computing , 118, 108554. Retrieved from https://doi.org/10.1016/j.asoc.2022.108554