Sharon Bruckner [1] (FU Berlin)

In this talk I present work done by Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier, Sven Thiel, and Johannes Uhlmann and myself on the the Colorful Components problem.
Given a vertex-colored graph, we want to delete a minimum number of edges such that no connected component contains two vertices of the same color. This problem has applications in many fields such as biology (multiple sequence alignment, network alignment) and data mining (the wikipedia language graph). We show that Colorful Components is polynomial-time solvable for two colors, but NP-hard already for three colors or on binary trees. On the positive side, we give a fixed-parameter algorithm for trees with running time 2^{c}n^{O(1)}, where c is the number of colors and n is the number of vertices in the tree. For general graphs G, we give a fixed-parameter algorithm with running time O((c-1)^k|G|), where k is the number of edges to delete. As additional solving strategies, we present polynomial-time data reduction rules, an ILP formulation, and a formulation as implicit hitting set problem. We present experiments with real-world data, compare the solution methods above and discuss our results and future plans.

Back to the research colloquium site. [2]