C O N V E X R E C O L O R I N G

This page is still under construction!

Definition

Given a necklace of colored beads, we say that the string is convex if all beads of the same color are in one chunk. In graph theory terms, we can view the necklace as a path and the coloring C as function from V to the set of colors C . Then C is convex if every subset of vertices belonging to the same color class is connected .
However, when the coloring is not convex, we would like to find the closest coloring C' that is convex. This distance between the two colorings C' and C dependes on the model assumed. Under the simplest model this is just the number of vertices whose color is changed between C' and C . It can be shown that under this model, it is enough to uncolor this set of vertices and obtain a partial convex coloring.
For further details see publications.

History

The motivation to the problem came from phylogenetics (The description of the evolution of a group of species by a tree , see e.g.Charles Darwin's Origin of Species (publ. 1859)). At this first stage, we considered only total C (i.e. all vertices are colored). However, very shortly we noticed that the problem very elegantly and naturally generalized to partial coloring, or specialized to a simple path or leaf colored trees.
The proof of hardness of the simplest case, led to the developments of approximation and fixed parameter algorithms (FPT) for various types of the problem.
CR has been the subject of M.Sc. and Ph.D. students around the world.

Contest

The developments of FPT algorithms for the problem drew Mike Fellows'es interest. CR is now featuring in the FPT community (along with VC, FVS, etc.) as a target to a race for the fastest FPT algorithm.

Worldwide

Researchers involved in C O N V E X R E C O L O R I N G