Stefano Quer e Lorenzo Cardone vincono l'ICSOFT Best Paper Award 2026

Stefano Quer e Lorenzo Cardone sono stati insigniti del premio ICSOFT Best Paper Award 2026, in occasione della 21st International Conference on Software Technologies (ICSOFT 2026), tenutasi a Porto (Portogallo) dal 16 al 18 luglio 2026.

Il premio è stato assegnato per l'articolo Cooperative Multi-Heuristic Parallelization for the Maximum Common Induced Subgraph Problem, pubblicato nei "Proceedings of the 21st International Conference on Software Technologies (ICSOFT 2026)".

Abstract dell'articolo
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 using 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.