Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Strong intractability results for generalized convex recoloring problems

Full text
Moura, Phablo F. S. [1] ; Wakabayashi, Yoshiko [2]
Total Authors: 2
[1] Univ Estadual Campinas, Inst Computacao, Campinas - Brazil
[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
Total Affiliations: 2
Document type: Journal article
Source: DISCRETE APPLIED MATHEMATICS; v. 281, n. SI, p. 252-260, JUL 15 2020.
Web of Science Citations: 0

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)

FAPESP's process: 16/21250-3 - Algorithmic and structural aspects of Covering and Packing problems on graphs
Grantee:Phablo Fernando Soares Moura
Support Opportunities: Scholarships in Brazil - Post-Doctoral
FAPESP's process: 17/22611-2 - Algorithmic and structural aspects of covering and packing problems on graphs
Grantee:Phablo Fernando Soares Moura
Support Opportunities: Scholarships abroad - Research Internship - Post-doctor
FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:Flávio Keidi Miyazawa
Support Opportunities: Research Projects - Thematic Grants