A heuristic for the convex recoloring problem in graphs

We consider a coloring as a function that assigns a color to a vertex, regardless of the color of its neighbors. In this sense, a coloring is said to be convex if every set of all same colored vertices induces a connected subgraph. The Convex Recoloring Problem finds the minimum number of recolored...

Full description

Saved in:
Bibliographic Details
Published in:International transactions in operational research 2022-05, Vol.29 (3), p.1454-1478
Main Authors: Dantas, Ana Paula S., de Souza, Cid C., Dias, Zanoni
Format: Article
Language:English
Subjects:
Adaptive search techniques
Apexes
Color
Coloring
combinatorial optimization
convex recoloring
Graph theory
Graphs
GRASP
Heuristic
Integer programming
Linear programming
Operations research
Trees (mathematics)
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider a coloring as a function that assigns a color to a vertex, regardless of the color of its neighbors. In this sense, a coloring is said to be convex if every set of all same colored vertices induces a connected subgraph. The Convex Recoloring Problem finds the minimum number of recolored vertices needed to turn a coloring convex. This problem is most commonly studied considering trees due to its origins in Computational Biology, but in this paper, we focus on general graphs. We propose a heuristic based on the Greedy Randomized Adaptive Search Procedure to solve the problem. We present computational experiments for our heuristic and compare it to an Integer Linear Programming (ILP) model from the literature. In these experiments, our heuristic recolored at most one vertex more than the ILP model, and it was also able to give better solutions when the ILP model was unable to find the optimal solution within the time limit. We also introduce a set of benchmark instances for the problem.
ISSN:0969-6016
1475-3995
DOI:10.1111/itor.12896