R.A. Kochkarov1, A.V. Timoshenko2, A.M. Kazancev3, A.M. Kochkarov4, A.A. Omelshin5

1–3 Financial University under the Government of the Russian Federation (Moscow, Russia)
4 North Caucasian State Academy (Cherkessk, Russia)
5 Military University of Radio Electronics (Cherepovets, Russia)
1 rkochkarov@fa.ru

Ensuring the structural and functional stability and integrity of spatially distributed information monitoring systems under the influence of destabilizing factors requires optimization procedures, the mathematical basis of which is, among other things, the solution of NP-complete problems. The urgency of the problem is due to the limited applicability of known discrete optimization methods for spatially distributed large-dimensional systems modeled on the basis of prefractal graphs.

Development of a methodology for investigating NP-complete problems for spatially distributed large-dimensional monitoring information systems based on the adaptation of classical NP-complete problems on large prefractal graphs.

A method for solving partial statements of NP-complete problems on large prefractal graphs is proposed, which takes into account the properties of self-similarity and the hierarchical structure of prefractal graphs and includes successive stages of dividing the problem into hierarchical subtasks, recursively solving these subtasks and constructing a global solution based on them.

The proposed technique makes it possible to reduce computational complexity when solving optimization statements of NP-complete problems on large graphs, which makes it applicable to ensure the structural and functional stability and integrity of spatially distributed monitoring information systems under the influence of destabilizing factors.

Kochkarov R.A., Timoshenko A.V., Kazancev A.M., Kochkarov A.M., Omelshin A.A. Solution of NP-complete problems of ensuring structural and functional stability of spatially distributed information monitoring systems. Dynamics of complex systems. 2025. V. 19. № 5. P. 57−68. DOI: 10.18127/j19997493-202505-07 (in Russian).

1. Kochkarov R.A., Chirov D.S., Timoshenko A.V., Kazancev A.M. Model` prostranstvenno-raspredelennoj informacionnoj sistemy` neprery`vnogo monitoringa s predfraktal`noj dinamicheskoj strukturoj v usloviyax vozdejstviya destabiliziruyushhix faktorov. T-Comm: Telekommunikacii i transport. 2025. T. 19. № 1. S. 4–12. DOI 10.36724/2072-8735-2025-19-1-4-12
2. Kochkarov R.A., Baldy`chev M.T., Kazancev A.M. i dr. Algoritm ocenki strukturno-funkcional`noj ustojchivosti i celostnosti geterogennoj seti peredachi danny`x prostranstvenno-raspredelennoj sistemy` monitoring. Trudy` MAI. 2024. № 137.
3. Shevczov V.A., Kazancev A.M., Timoshenko A.V. i dr. Pokazatel` strukturnoj e`ffektivnosti upravleniya informacionny`m vzaimodejstviem v geterogennoj seti peredachi danny`x prostranstvenno-raspredelennoj sistemy` monitoring. Vestnik Voronezhskogo gosudarstvennogo texnicheskogo universiteta. 2024. T. 20. № 2. S. 124–131. DOI 10.36622/1729-6501.2024.20.2.019
4. Kochkarov R.A., Kochkarov A.A. Teoretiko-grafovy`j algoritm dinamicheskogo naznacheniya sredstv sistemy` neprery`vnogo monito­ring. Uspexi sovremennoj radioe`lektroniki. 2023. T. 77. № 9. S. 44–50. DOI 10.18127/j20700784-202309-05
5. Kirkpatrick S., Gelatt C.D. & Vecchi M.P. Optimization by Simulated Annealing. Science. 1983. № 220(4598). P. 671–680.
6. Sörensen K. Metaheuristics for the Vehicle Routing Problem: A Review. Transportation Science. 2015. № 49 (3). P. 637–657.
7. Ge`ri M., Dzhonson D. Vy`chislitel`ny`e mashiny` i trudnoreshaemy`e zadachi: per. s angl. M.: Mir. 1982. 416 s.
8. Xarari F. Teoriya grafov: per. s angl. M.: Mir. 1973. 301 s.
9. Karci A. Efficiency and Inefficiency Assessment of Graph Nodes for NP-Complete Problems.
10. Huh J.-H., Hwa J. & Seo Y.-S. Hierarchical System Decomposition Using Genetic Algorithm for Future Sustainable Computing. Sustai­nability. 2020. № 12 (6). P. 2177–2209. DOI: 10.3390/su12062177 MDPI
11. Hertz A. Polynomially solvable classes for the maximum stable set problem. Discrete Applied Mathematics. 1995. № 60. P. 195–210. DOI: 10.1016/0166-218X(94)00051-E
12. Hertz A. On the use of boolean methods for the computation of the stability number. Discrete Applied Mathematics. 1997. № 76. P. 183–203. DOI: 10.1016/S0166-218X(96)00124-2
13. Golumbic M.C. Algorithmic graph theory and perfect graphs. New-York: Academic Press. 1980. 284 p. DOI: 10.1016/C2013-0-10739-8
14. Grotschel M., Lovasz L., Schrijver A. Polynomial algorithms for perfect graphs. Annals of Discrete Mathematics. 1984. № 21. P. 325–356. DOI: 10.1016/S0304-0208(08)72943-8
15. Ajzerman M.A., Gusev L.A., Petrov S.V., Smirnova I.M., Tenenbaum L.A. Dinamicheskij podxod k analizu struktur, opisy`vaemy`x grafami (osnovy` grafodinamiki). Issledovaniya po teorii struktur. M.: Nauka. 1988. S. 5–76.
16. Iordanskij M.A. Konstruktivnaya klassifikaciya grafov. Modelirovanie i analiz informacionny`x sistem. 2012. № 19 (4). C. 144–153. DOI: 10.18255/1818-1015-2012-4-144-153
17. Makarenko S.I. Modeli sistemy` svyazi v usloviyax prednamerenny`x destabiliziruyushhix vozdejstvij i vedeniya razvedki: monografiya. SPb.: Naukoemkie texnologii. 2020. 337 s.
18. Timoshenko A.V., Kochkarov R.A., Kochkarov A.A. Vy`delenie uslovij razreshimosti NP-polny`x zadach dlya klassa predfraktal`ny`x grafov. Modelirovanie i analiz informacionny`x sistem. 2021. T. 28. № 2. S. 126–135. DOI: 10.18255/1818-1015-2021-2-126-135
19. Kochkarov R.A. Zadachi mnogokriterial`noj optimizacii na mnogo-vzveshenny`x predfraktal`ny`x grafax. M.: Akademinnovaciya. 2014. 189 s.
20. Kochkarov A.M. Raspoznavanie fraktal`ny`x grafov. Algoritmicheskij podxod. Nizhnij Arxy`z: RAN SAO. 1998. 170 s.
21. Prokof`ev B.C., Maly`shev V.A. Nechetkie algoritmy` planirovaniya raspredeleniya resursov sistemy` upravleniya voennogo naznacheniya. Vestnik Voronezh. in-ta vy`sok, texnol. 2008. № 3. S. 50–53.
22. Aziz F., Akbar M.S., Jawad M., Malik A.H., Uddin M.I., Gkoutos G.V. Graph characterisation using graphlet-based entropies. Pattern Recognition Letters. 2021. № 147. P. 100–107. DOI: 10.1016/j.patrec.2021.03.031
23. Aziz F., Ullah A., Shah F. Feature selection and learning for graphlet kernel. Pattern Recognition Letters. 2020. № 136. P. 63–70. DOI: 10.1016/j.patrec.2020.05.023
24. Kas`yanov V.N., Kas`yanova E.V. Model` atributirovanny`x ierarxicheskix grafov s portami dlya vizualizacii slozhno strukturirovannoj informacii. Sb. nauch. tr. XXI otkry`toj Vseros. konf. «Prepodavanie informacionny`x texnologij v Rossijskoj Federacii». Nizhnij Novgorod, 18–19 maya 2023 g. Nizhnij Novgorod: Izdatel`stvo Nizhegorodskogo gosudarstvennogo universiteta im. N.I. Lobachevskogo. 2023. S. 53–54.
25. Kochkarov A.A., Kalashnikov N.V., Kochkarov R.A. Sravnitel`ny`j analiz algoritmov vy`yavleniya soobshhestv v slozhny`x setevy`x sistemax na primere social`ny`x setej. Programmny`e produkty` i sistemy`. 2020. № 2. S. 349–356. DOI: 10.15827/0236-235X.130.349-356
26. Pisinger D. & Ropke S. A General Variable Neighborhood Search Heuristic for the Periodic Vehicle Routing Problem. Computers & Opera­tions Research. 2007. № 34 (11). P. 3252–3268.
27. Sirota A.A. Komp`yuternoe modelirovanie i ocenka e`ffektivnosti slozhny`x sistem. M.: Texnosfera. 2006. 280 s.
28. Axo A.V., Xopkroft D.E`. i dr. Struktury` danny`x i algoritmy`. M.: Vil`yams. 2007. 400 s.
29. Moreno L.Q. Graphlets and Motifs in Biological Networks. Encyclopedia of Bioinformatics and Computational Biology. 2019. № 2.
30. P. 814–820. DOI: 10.1016/B978-0-12-809633-8.20291-4
31. Alekseev V.E. Issledovanie kolichestvenny`x i slozhnostny`x xarakteristik nasledstvenny`x klassov grafov: avtoreferat diss. ... doktora fiziko-matematicheskix nauk: 01.01.09. Nizhnij Novgorod: Nizhegor. gos. un-t im. N. I. Lobachevskogo. 2002. 14 s.
32. Nogin V.D. Prinyatie reshenij v mnogokriterial`noj srede: kolichestvenny`j podxod. M.: FIZMATLIT. 2002. 144 s.
33. Podinovskij V.V., Nogin V.D. Pareto-optimal`ny`e resheniya mnogokriterial`ny`x zadach. M.: Vy`sshaya shkola. 1982. 256 s.
34. Malineczkij G.G., Kochkarov A.A., Kochkarov R.A. Nekotory`e aspekty` dinamicheskoj teorii grafov. Zhurnal vy`chislitel`noj matematiki i matematicheskoj fiziki. 2015. T. 55. № 9. S. 1623–1629. DOI: 10.7868/S0044466915090094
35. Dorozhko I.V., Osipov N.A. Metodika sinteza optimal`ny`x strategij diagnostirovaniya avtomatizirovanny`x sistem upravleniya slozhny`mi texnicheskimi ob``ektami s ispol`zovaniem apriornoj informacii. Trudy` SPIIRAN. 2012. № 1(20). S. 165–185.
36. Kochkarov A.A., Salpagarov M.B., Kochkarov R.A. Modelirovanie razrusheniya slozhny`x sistem s aciklicheskoj strukturoj. Upravlenie bol`shimi sistemami: sb. tr. 2007. № 17. S. 103–120.
37. Ford L., Falkerson D. Potoki v setyax. M.: Mir. 1966. 276 s.