Strong inequalities and a branch-and-price algorithm for the convex recoloring problem

Manoel Campêlo, Alexandre S. Freire, Phablo F.S. Moura and Joel C. Soares

European Journal of Operational Research, 2022, vol. 303, issue 1, 54-65

Abstract: A coloring of the vertices of a connected graph is convex if each color class induces a connected subgraph. We address the convex recoloring problem: Given a connected graph G and a coloring of its vertices, recolor a minimum number of vertices of G so that the resulting coloring is convex. The convex recoloring problem (or CR, for short) was firstly motivated by applications on perfect phylogenies, and it is a hard computational problem even restricted to paths. In this work, we introduce a polytope based on connected subgraphs for CR and propose a class of strong inequalities with righthand side ranging from 1 to the number of colors. Those with righthand side one generalize and strengthen the inequalities of the corresponding formulation and comprise all facet-defining inequalities on binary coefficients when G is a tree. We report on computational experiments for an application on mobile networks to evaluate the potential of the proposed inequalities to reduce the integrality gap. Finally, we propose a branch-and-price algorithm to solve CR on trees and present the results of experiments on several classes of instances, including phylogenetic trees. The experiments indicate that our approach outperforms the fastest solving method in the literature.

Keywords: Integer programming; Convex recoloring; Branch-and-price; Polyhedral study; Phylogenetic tree (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172200114X
Full text for ScienceDirect subscribers only

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:eee:ejores:v:303:y:2022:i:1:p:54-65

DOI: 10.1016/j.ejor.2022.02.013

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().