Backbone Analysis and Applications in Heuristic Algorithm Design

As the shared common parts of all global optimal solutions to an NP-hard problem instance, the backbone has become a hot research line due to its essential impacts on the heuristic algorithm design. In this paper, research results on the backbone and related conceptions were thoroughly surveyed. The existing research of backbone consists of three areas, including the basic theoretical research focusing on investigation of the relationship between the backbone and computational complexity, the application research on how to e-ciently approximate the backbone, and the applications on how to employ the backbone within the heuristic algorithm design. Furthermore, we discussed in detail the existing problems to be solved in this topic, and provided some guidelines on how to tackle them.