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

Wen Sun, Jin-Kao Hao () and Alexandre Caminada
Additional contact information
Wen Sun: Université d’Angers
Jin-Kao Hao: Université d’Angers
Alexandre Caminada: UTBM

Journal of Heuristics, 2019, vol. 25, issue 4, No 4, 565-590

Abstract: Abstract Given an undirected graph $$G = (V,E)$$ 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$$ χ ( H ) = k ), and removing any vertex causes a decrease of $$\chi (H)$$ χ ( H ) . The k-VCS problem (k-VCSP) is to find the smallest k-vertex-critical subgraph $$H^*$$ 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.

Keywords: Vertex-critical subgraph; Graph coloring; Tabu search; Backtracking-based diversification; Irreducibly inconsistent systems (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-017-9358-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:25:y:2019:i:4:d:10.1007_s10732-017-9358-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-017-9358-5

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().