The colorful components framework is motivated by applications emerging from computational biology. A vertex-colored graph G is said to be colorful if every color appears exactly once. The general goal is to remove a collection of edges from an undirected vertex-colored graph G such that in the resulting graph H all the connected components are colorful. We want H to optimize an appropriate objective function. Two natural functions involve deleting the smallest number of edges (which we refer to as Colorful Components) and maximizing the number of edges in the transitive closure of the remaining components (which we refer to as MEC). These problems are well-studied from the point of view of classical complexity, approximation algorithms, and parameterized algorithms. We complement and improve on some of the results in the literature concerning MEC and Colorful Components. In the context of MEC, we demonstrate a linear kernel on trees and a randomized k~(O(|k)) algorithm, where k is the standard parameter. Both of these results directly improve on previously known results about the problem. For the Colorful Components problem, we demonstrate a FPT algorithm for the vertex cover parameter, which is a well-motivated structural parameterization given that the problem is already para-NP-hard when parameterized by a deletion set to a disjoint union of stars.
展开▼
