Please use this identifier to cite or link to this item:
|Title:||Strong intractability results for generalized convex recoloring problems|
|Abstract:||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 firstly investigated on trees and for r=1, motivated by applications on perfect phylogenies. The more general 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. In this work, 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 parameterized versions of the problem|
Teoria dos grafos
|Appears in Collections:||IC - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.