On Graph Motif Problems Parameterized by Dual

Christian Komusiewicz (FSU Jena)

The Graph Motif problem has as input a vertex-colored graph $G=(V,E)$ with k different vertex colors and asks whether there is a connected subgraph on $k$ vertices containing each color exactly once. We study Graph Motif parameterized by $\ell:=|V|-k$.

For general graphs we show that, assuming the strong exponential time hypothesis, a previous $O(2^\ell\cdot |E|)$-time algorithm is optimal. We then provide a faster algorithm for trees. We also consider the List-Colored Graph Motif problem. In this extension of Graph Motif each vertex may choose its color from a list of colors. For this variant, we strengthen previous hardness results by showing for example that the problem remains W[1]-hard when the color lists have length at most two.
Finally, we report on further positive and negative results for the special case that $G$ is a tree.

(This is joint work with Guillaume Fertin, Université de Nantes.)

Back to the research colloquium site.