Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Strong intractability results for generalized convex recoloring problems

Texto completo
Autor(es):
Moura, Phablo F. S. [1] ; Wakabayashi, Yoshiko [2]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Computacao, Campinas - Brazil
[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: DISCRETE APPLIED MATHEMATICS; v. 281, n. SI, p. 252-260, JUL 15 2020.
Citações Web of Science: 0
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
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 17/22611-2 - Aspectos algorítmicos e estruturais de problemas de cobertura e empacotamento em grafos
Beneficiário:Phablo Fernando Soares Moura
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - 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
Linha de fomento: Auxílio à Pesquisa - Temático