Advertisement
Published in:
2013 | OriginalPaper | Chapter
On the Complexity of Solving or Approximating Convex Recoloring Problems
Authors : Manoel B. Campêlo, Cristiana G. Huiban, Rudini M. Sampaio, Yoshiko Wakabayashi
Published in: Computing and Combinatorics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.