  The quest for colorful components (connected components where each color is
associated with at most one vertex) inside a vertex-colored graph has been
widely considered in the last ten years. Here we consider two variants, Minimum
Colorful Components (MCC) and Maximum Edges in transitive Closure (MEC),
introduced in 2011 in the context of orthology gene identification in
bioinformatics. The input of both MCC and MEC is a vertex-colored graph. MCC
asks for the removal of a subset of edges, so that the resulting graph is
partitioned in the minimum number of colorful connected components; MEC asks
for the removal of a subset of edges, so that the resulting graph is
partitioned in colorful connected components and the number of edges in the
transitive closure of such a graph is maximized. We study the parameterized and
approximation complexity of MCC and MEC, for general and restricted instances.
  For MCC on trees we show that the problem is basically equivalent to Minimum
Cut on Trees, thus MCC is not approximable within factor $1.36 - \varepsilon$,
it is fixed-parameter tractable and it admits a poly-kernel (when the parameter
is the number of colorful components). Moreover, we show that MCC, while it is
polynomial time solvable on paths, it is NP-hard even for graphs with constant
distance to disjoint paths number. Then we consider the parameterized
complexity of MEC when parameterized by the number $k$ of edges in the
transitive closure of a solution (the graph obtained by removing edges so that
it is partitioned in colorful connected components). We give a fixed-parameter
algorithm for MEC paramterized by $k$ and, when the input graph is a tree, we
give a poly-kernel.
