direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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.)

Christian Komusiewicz
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras