Strong intractability of generalized convex recoloring problems

A coloring of the vertices of a connected graph is r-convex if each color class induces a subgraph with at most r components. We address the r-convex recoloring problem defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G so that the resulting coloring is r-convex. This problem, known to be NP-hard even on paths, was first investigated on trees and for r=1, motivated by applications on perfect phylogenies. The concept of r-convexity, for r≥2, was proposed later, and it is also of interest in the study of protein-protein interaction networks and phylogenetic networks. Here, we show that, for each r∈N, the r-convex recoloring problem on n-vertex bipartite graphs cannot be approximated within a factor of n1−ε for any ε>0, unless P=NP. We also provide strong hardness results for weighted and parametrized versions of the problem.