Cooperative Multi-Heuristic Parallelization for the Maximum Common Induced Subgraph Problem

Abstract

: The Maximum Common Induced Subgraph problem is a central challenge in combinatorial optimization, with applications across diverse fields. Its NP-hard nature has led to a long line of branch-and-bound algorithms, among which the McSplit family stands out for its search-space representation and effective pruning. More recent extensions, such as McSplit-DAL, integrate Domain Action Learning to guide branching decisions us-ing dynamic reward functions. However, they remain essentially sequential and rely on a single heuristic configuration, underutilizing modern multi-core architectures and heuristic diversification. In this work, we introduce CP-McSplitDAL, a cooperative parallel framework that extends McSplit-DAL with portfolio-style multi-heuristic search on shared-memory machines. The original recursive algorithm is reformulated as an iterative engine, enabling explicit management of search states, load sharing among threads, and controlled thread migration between heuristics. Each context couples a topological vertex-ranking metric with a specific ordering scheme and learns its own reward landscape. Cooperation is achieved through a globally shared variable that represents the size of the largest solution found so far, enabling cross-heuristic pruning and adaptive reward handling, and supporting both unified and distributed matrices. At the same time, a master evaluation periodically decays rewards and deactivates under-performing heuristics, shifting from early diversification to late exploitation. We evaluate CP-McSplitDAL on standard benchmarks, including small instances solvable to optimality and a large set of real-world graph pairs. The results show that our cooperative multi-heuristic configuration achieves lower regret in time to optimality, improves solution quality under time limits, and better exploits multi-core hardware than non-cooperative or purely sequential variants.