Application of the task of finding the minimum vertex coverage in a graph to improve the robustness of digital identity system

This paper examines the features of building digital identity systems for managing information technology processes in an enterprise, the architecture of which depends on decentralized data registers - blockchains. The paper considers blockchains as weighted graphs and formulates a number of theses that speak about the specifics of the functioning of such distributed networks in real information technology enterprises. The features of various network topologies and possible architectural vulnerabilities and flaws that can affect the operation of the entire network are considered – centralization of mining, centralization of staking, various attacks on a functioning network (topological and 51% percent attack). Blockchains using various consensus-building algorithms, taking into account their features, are considered. The paper considers the task of finding the minimum coverage in a graph and emphasizes the importance of applying this task to the described digital personality system in order to increase the reliability of the blockchain computer network by analyzing its topology. Various methods of finding the minimum coverage in a graph are considered – exact and heuristic algorithms. The paper analyzes an application that implements the ant colony algorithm to solve the problem, provides numerical characteristics of the algorithm and its formal description.

1. Akutin A.S. Tekhnologiya suverennoi lichnosti kak novyi podkhod v obrabotke personal'nykh dannykh. In: Problemy upravleniya v sotsial'no-ekonomicheskikh i tekhnicheskikh sistemakh: materialy XIX Mezhdunarodnoi nauchno-prakticheskoi konferentsii, 13–14 April 2023, Saratov, Russia. Saratov: ITs "Nauka"; 2023. P. 128–134. (In Russ.).

2. Akutin A.S., Denisova Z.P. Tekhnologiya tsifrovoi lichnosti v upravlenii tekhnologicheskim predpriyatiem. In: Problemy upravleniya v sotsial'no-ekonomicheskikh i tekhnicheskikh sistemakh: materialy XX Mezhdunarodnoi nauchno-prakticheskoi konferentsii: sbornik nauchnykh statei, 17–18 April 2024, Saratov, Russia. Saratov: ITs "Nauka"; 2024. P. 154–156. (In Russ.).

3. Vayadande K., Baviskar A., Avhad J., Bahadkar S., Bhalerao P., Chimkar A. A Comprehensive Review on Navigating the Web 3.0 Landscape. In: 2024 Second International Conference on Inventive Computing and Informatics (ICICI), 11–12 June 2024, Bangalore, India. IEEE; 2024. P. 456–463. https://doi.org/10.1109/ICICI62254.2024.00080

4. Nakamoto S. Bitcoin: A Peer-to-Peer Electronic Cash System. SSRN. URL: https://doi.org/10.2139/ssrn.3440802 [Accessed 4th February 2025].

5. Van Ditmarsch H., Gattinger M., Ramezanian R. Everyone Knows That Everyone Knows: Gossip Protocols for Super Experts. Studia Logica. 2023;111(3):453–499. https://doi.org/10.1007/s11225-022-10032-3

6. Song W., Zhang W., Wang J., Zhai L., Jiang P., Huang Sh. Blockchain Data Analysis from the Perspective of Complex Networks: Overview. Tsinghua Science and Technology. 2023;28(1):176–206. https://doi.org/10.26599/TST.2021.9010080

7. Gochhayat S.P., Shetty S., Mukkamala R., Foytik P., Kamhoua G.A., Njilla L. Measuring Decentrality in Blockchain Based Systems. IEEE Access. 2020;8:178372–178390. https://doi.org/10.1109/ACCESS.2020.3026577

8. Madine M., Salah Kh., Jayaraman R., Al-Hammadi Yo., Arshad J., Yaqoob I. appXchain: Application-Level Interoperability for Blockchain Networks. IEEE Access. 2021;9:87777–87791. https://doi.org/10.1109/ACCESS.2021.3089603

9. Akutin A.S., Brovko A.V. Decentralized Data Registry in Sovereign Identity Technology. Engineering Journal of Don. 2023;(6):232–246. (In Russ.).

10. Vega F. The Minimum Vertex Cover Problem. [Preprint]. ResearchGate. URL: https://www.researchgate.net/publication/388526292_The_Minimum_Vertex_Cover_Problem [Accessed 13th February 2025].

11. Jayabalasamy G., Pujol C., Latha Bhaskaran K. Application of Graph Theory for Blockchain Technologies. Mathematics. 2024;12(8). https://doi.org/10.3390/math12081133

12. Barabási A.-L., Albert R. Emergence of Scaling in Random Networks. Science. 1999;286(5439):509–512.

13. Xiao M., Nagamochi H. Exact Algorithms for Maximum Independent Set. Information and Computation. 2017;255:126–146. https://doi.org/10.1016/j.ic.2017.06.001

14. Åstrand M., Floréen P., Polishchuk V., Rybicki J., Suomela J., Uitto J. A Local 2-Approximation Algorithm for the Vertex Cover Problem. In: Distributed Computing: 23rd International Symposium, DISC 2009: Proceedings, 23–25 September 2009, Elche, Spain. Berlin, Heidelberg: Springer; 2009. P. 191–205. https://doi.org/10.1007/978-3-642-04355-0_21

15. Shyu Sh.J., Yin P.-Ye., Lin B.M.T. An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem. Annals of Operations Research. 2004;131:283–304. https://doi.org/10.1023/B:ANOR.0000039523.95673.33