Recursive-Parallel Algorithm for Solving the Maximum Common Subgraph Problem
https://doi.org/10.18255/1818-1015-2023-2-128-139
EDN: NPFBHC
Abstract
The paper proposes an algorithm for solving the problem of finding the maximum common subgraph. Both the sequential and the parallel version of the algorithm, their software implementation are described, and an experimental study of their effectiveness is carried out.
This problem is one of the most famous NP-complete problems. Its solution may be required when solving many practical problems related to the study of complex structures. We solve it in a statement when we need to find all possible isomorphisms of the found common subgraph. Due to the extremely high complexity of the problem, it is natural to want to speed up its solution by parallelizing the algorithm.
To organize parallel computing, the author used the RPM_ParLib library. It allows to develop effective applications for parallel computing on a local network under the control of the runtime environment .NET Framework.The library supports a recursive-parallel programming style and provides effective work distribution and dynamic load balancing of computational modules during program execution. It can be used for applications written in any programming language supported by the .NET Framework.
The purpose of the numerical experiment was to study the acceleration achieved due to the recursive-parallel organization of calculations. For the experiment, the author developed a special application in the C# language designed to generate various sets of initial data with specified parameters. The paper describes the features of the generated initial pairs of graphs, as well as the results obtained during the experiment.
This problem is one of the most famous NP-complete problems. Its solution may be required when solving many practical problems related to the study of complex structures. We solve it in a statement when we need to find all possible isomorphisms of the found common subgraph. Due to the extremely high complexity of the problem, it is natural to want to speed up its solution by parallelizing the algorithm.
To organize parallel computing, the author used the RPM_ParLib library. It allows to develop effective applications for parallel computing on a local network under the control of the runtime environment .NET Framework.The library supports a recursive-parallel programming style and provides effective work distribution and dynamic load balancing of computational modules during program execution. It can be used for applications written in any programming language supported by the .NET Framework.
The purpose of the numerical experiment was to study the acceleration achieved due to the recursive-parallel organization of calculations. For the experiment, the author developed a special application in the C# language designed to generate various sets of initial data with specified parameters. The paper describes the features of the generated initial pairs of graphs, as well as the results obtained during the experiment.
About the Author
Vladimir V. Vasilchikov
P. G. Demidov Yaroslavl State University
Russian Federation
Russian Federation
References
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.
Review
For citations:
Vasilchikov V.V. Recursive-Parallel Algorithm for Solving the Maximum Common Subgraph Problem. Modeling and Analysis of Information Systems. 2023;30(2):128-139. (In Russ.) https://doi.org/10.18255/1818-1015-2023-2-128-139. EDN: NPFBHC
Views:
316
Email this article 