Iterated backtrack removal search for finding k-vertex-critical subgraphs

Given an undirected graph G = (V, E) and a positive integer k, a k-vertex-critical subgraph (k-VCS) of G is a subgraph H such that its chromatic number equals k (i.e., chi(H) = k), and removing any vertex causes a decrease of chi(H). The k-VCS problem (k-VCSP) is to find the smallest k- vertex-critical subgraph H* of G. This paper proposes an iterated backtrack-based removal (IBR) heuristic to find k-VCS for a given graph G. IBR extends the popular removal strategy that is intensification-oriented. The proposed extensions include two new diversification-oriented search components-a backtracking mechanism to reconsider some removed vertices and a perturbation strategy to escape local optima traps. Computational results on 80 benchmark graphs show that IBR is very competitive in terms of solution quality and run-time efficiency compared with state-of-the-art algorithms in the literature. Specifically, IBR improves the best-known solutions for 9 graphs and matches the best results for other 70 instances. We investigate the interest of the key components of the proposed algorithm.