Рекурсивно-параллельный алгоритм поиска максимального общего подграфа

В работе предложен алгоритм решения задачи нахождении максимального общего подграфа. Описаны последовательный и параллельный вариант алгоритма, их программная реализация и произведено экспериментальное исследование их эффективности. Данная задача является одной из самых известных NP"=полных задач. Ее решение может потребоваться при решении многих практических задач, связанных с исследованием сложных структур. Мы решаем ее в постановке, в которой требуется найти все возможные изоморфизмы найденного общего подграфа. Ввиду чрезвычайно высокой трудоемкости задачи желание ускорить ее решение за счет распараллеливания алгоритма является вполне естественным. Для организации параллельных вычислений автором использовалась библиотека RPM_ParLib, которая позволяет создавать параллельные приложения, работающие в локальной вычислительной сети под управлением среды исполнения .NET Framework. Библиотека поддерживает рекурсивно-параллельный стиль программирования и обеспечивает эффективное распределение работы и динамическую балансировку загрузки вычислительных модулей в процессе исполнения программы. Она может быть использована для приложений, написанных на любом языке программирования, поддерживаемом .NET Framework. Целью численного эксперимента было исследование ускорения, достигаемого за счет рекурсивно"=параллельной организации вычислений. Для эксперимента автором было разработано специальное приложение на языке C#, предназначенное для генерации различных наборов исходных данных с заданными параметрами. В работе описаны характеристики сгенерированных исходных пар графов, а также результаты, полученные в ходе эксперимента.

1. M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Siam Review, vol. 24, no. 1, pp. 90–91, 1982.

2. R. Hoffmann, C. McCreesh, and C. Reilly, “Between Subgraph Isomorphism and Maximum Common Subgraph,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2017, vol. 31, no. 1, pp. 3907–3914.

3. S. N. Ndiaye and C. Solnon, “CP Models for Maximum Common Subgraph Problems,” Lecture Notes in Computer Science, vol. 6876, pp. 637–644, 2011.

4. D. Conte, P. Foggia, and M. Vento, “Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs,” Journal of Graph Algorithms and Applications, vol. 11, no. 1, pp. 99–143, 2007.

5. J. J. McGregor, “Backtrack search algorithms and the maximal common sub-graph problem,” Software: Practice and Experience, vol. 12, no. 1, pp. 23–34, 1982.

6. L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “An Improved Algorithm for Matching Large Graphs,” in Proc. of the 3rd IAPR-TC-15 InternationalWorkshop on Graph-based Representations, 2001, pp. 149–159.

7. P. J. Durand, R. Pasari, J. W. Baker, and C.-che Tsai, “An efficient algorithm for similarity analysis of molecules,” Internet Journal of Chemistry, vol. 2, no. 17, pp. 1–16, 1999.

8. C. Bron and J. Kerbosch, “Algorithm 457: finding all cliques of an undirected graph,” Communications of the ACM, vol. 16, no. 9, pp. 575–577, 1973.

9. A. Marcelli, S. Quer, and G. Squillero, “The Maximum Common Subgraph Problem: A Portfolio Approach.” 2019, [Online]. Available: http://arxiv.org/abs/1908.06418.

10. V. V. Vasilchikov, “Parallel algorithm for solving the graph isomorphism problem,” Modeling and analysis of information systems, vol. 27, no. 1, pp. 86–94, 2020.

11. V. V. Vasilchikov, “Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem,” Modeling and analysis of information systems, vol. 29, no. 1, pp. 30–43, 2022.

12. V. V. Vasilchikov, Sredstva parallelnogo programmirovaniya dlya vychislitelnykh sistem s dinamicheskoy balansirovkoy zagruzki. YarGU, Yaroslavl, 2001.

13. V. V. Vasilchikov, “On the recursive-parallel programming for the .NET framework,” Automatic Control and Computer Sciences, vol. 48, pp. 575–580, 2014.