Strong intractability results for generalized convex recoloring problems

Autor(es)

Moura, Phablo F. S. ; Wakabayashi, Yoshiko

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE APPLIED MATHEMATICS; v. 281, p. 9-pg., 2020-07-15.

Resumo

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 is an element of N, the r-convex recoloring problem on n-vertex bipartite graphs cannot be approximated within a factor of n(1-epsilon) for any epsilon > 0, unless P = NP. We also provide strong hardness results for weighted and parameterized versions of the problem. (c) 2019 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 16/21250-3 - Aspectos algorítmicos e estruturais de problemas de Cobertura e Empacotamento em grafos
• Beneficiário: Phablo Fernando Soares Moura
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 17/22611-2 - Aspectos algorítmicos e estruturais de problemas de cobertura e empacotamento em grafos
• Beneficiário: Phablo Fernando Soares Moura
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado