Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems

A vertex coloring of a tree is called

convex

if each color induces a connected component. The NP-hard

Convex Recoloring

problem on vertex-colored trees asks for a minimum-weight change of colors to achieve a convex coloring. For the non-uniformly weighted model, where the cost of changing a vertex

v

to color

c

depends on both

v

and

c

, we improve the running time on trees from

O

(

Δ

κ

·

κn

) to

O

(3

κ

·

κn

), where

Δ

is the maximum vertex degree of the input tree

T

,

κ

is the number of colors, and

n

is the number of vertices in

T

. In the uniformly weighted case, where costs depend only on the vertex to be recolored, one can instead parameterize on the number of

bad

colors

β

 ≤ 

κ

, which is the number of colors that do not already induce a connected component. Here, we improve the running time from

O

(

Δ

β

·

βn

) to

O

(3

β

·

βn

). For the case where the weights are integers bounded by

M

, using fast subset convolution, we further improve the running time with respect to the exponential part to

O

(2

κ

·

κ

4

n

2

M

log

2

(

nM

)) and

O

(2

β

·

β

4

n

2

M

log

2

(

nM

)), respectively. Finally, we use fast subset convolution to improve the exponential part of the running time of the related 1-

Connected Coloring Completion

problem.