On the Kernel­ization Complexity of Colorful Motifs

In Colorful Motifs, the vertices of a graph carry colors, and the task is to find a connected subgraph that uses every color exactly once. The problem comes from searching biological networks, and it is fixed-parameter tractable in the number of colors. I look at preprocessing. Even on simple trees called combs, polynomial kernels are unlikely (though combs do admit many small kernels), and rooting the motif does not rescue general trees. The problem stays NP-complete on graphs of diameter two, which shows that Connected Dominating Set is NP-complete there too and unlikely to have a polynomial kernel. Colorful Motifs is a handy source of hardness for connectivity problems.