Inhalt des Dokuments
Es gibt keine deutsche Übersetzung dieser Webseite.
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.)
Date | Speaker | Location | Language |
---|---|---|---|
22.10.2015 16:15 | Christian Komusiewicz | TEL 512 | english |