Please use this identifier to cite or link to this item:
Type: Artigo
Title: Strong intractability results for generalized convex recoloring problems
Author: Moura, P.F.S.
Wakabayashi, Y.
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
Subject: Análise filogenética
Teoria dos grafos
Country: Países Baixos
Editor: Elsevier
Rights: Fechado
Identifier DOI: 10.1016/j.dam.2019.08.002
Date Issue: 2020
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-85071122752.pdf558.96 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.