Comparison of the Efficiency of Different Approaches to Accelerating the Algorithm for Enumerating Minimal Dominating Sets
Abstract
The paper presents a comparative study of several implementations of the Magu algorithm for enumerating inclusion-minimal dominating sets in an undirected graph. Unlike the conventional approach, where parallelization is applied to a batch of independent computational runs, this work investigates internal parallelization of the algorithm itself when processing each graph. Five implementations are considered: a sequential PyPy-based version, multiprocessing, simplified multiprocessing, Numba + multiprocessing, and Numba + threads. In all parallel implementations, the construction of new terms for the current clause is parallelized. Computational experiments were carried out on random graphs with 15 to 30 vertices. For each value of n, 10 graphs were processed, and the average execution time per graph was used as the main performance metric. The results show that the sequential PyPy-based implementation provides the best performance. It is established that internal parallelization of the algorithm does not lead to acceleration for the considered graph sizes and in most cases significantly increases execution time. The main reasons are the overhead of splitting terms, transferring intermediate data, synchronizing workers, and repeatedly applying the absorption operation.