Turbo-charging dominating set with an FPT subroutine

Abstract

Turbo-charging is a recent algorithmic technique that is based on the fixed-parameter tractability of the dynamic versions of some problems as a way to improve heuristics. We demonstrate the effectiveness of this technique and develop the turbo-charging idea further. A new hybrid heuristic for the Dominating Set problem that further improves this method is obtained by combining the turbo-charging technique with other standard heuristic tools including Local Search (LS). We implement both the recently proposed “turbo greedy” algorithm of Downey et al. [8] and a new method presented in this paper. The performance of these new heuristics is assessed on three suites of benchmark datasets, namely DIMACS, BHOSLIB and KONECT. Experiments comparing our algorithm to both heuristic and exact algorithms demonstrate its effectiveness. Our algorithm often produced results that were either exact or better than all the other available algorithms.