Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
On the Complexity of Solving or Approximating Convex Recoloring Problems
verfasst von : Manoel B. Campêlo, Cristiana G. Huiban, Rudini M. Sampaio, Yoshiko Wakabayashi
Erschienen in: Computing and Combinatorics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given a graph with an arbitrary vertex coloring, the Convex Recoloring Problem (CR) consists of recoloring the minimum number of vertices so that each color induces a connected subgraph. We focus on the complexity and inapproximabiliy of this problem on
k
-colored graphs, for fixed
k
≥ 2. We prove a very strong complexity result showing that CR is already NP-hard on
k
-colored grids, and therefore also on planar graphs with maximum degree 4. For each
k
≥ 2, we also prove that, for a positive constant
c
, there is no
c
ln
n
-approximation algorithm even for
k
-colored
n
-vertex bipartite graphs, unless P = NP. For 2-colored (
q
,
q
− 4)-graphs, a class that includes cographs and
P
4
-sparse graphs, we present polynomial-time algorithms for fixed
q
. The same complexity results are obtained for a relaxation of CR, where only one fixed color is required to induce a connected subgraph.