Structural Parameter­izations for Colorful Components

In comparative genomics, genes across several genomes form a vertex-colored graph (one color per genome), and groups of orthologous genes should be colorful, with no color appearing twice. The Colorful Components problems delete edges so that every component ends up colorful, either deleting as few edges as possible (Colorful Components) or keeping as many edges as possible in the transitive closure (MEC). I improve known parameterized results for both. For MEC, I give a randomized k^O(k) algorithm based on color coding and a linear kernel on trees. For Colorful Components, which is para-NP-hard even with a deletion set to disjoint stars, I give an FPT algorithm parameterized by vertex cover.