Strong intractability results for generalized convex recoloring problems

Author(s)

Moura, Phablo F. S. ; Wakabayashi, Yoshiko

• Document type: Journal article
• Source: DISCRETE APPLIED MATHEMATICS; v. 281, p. 9-pg., 2020-07-15.

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 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: 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
• 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