When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2016.7
URN: urn:nbn:de:0030-drops-60837
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6083/
 Go to the corresponding LIPIcs Volume Portal

### Graph Motif Problems Parameterized by Dual

 pdf-format:

### Abstract

Let G=(V,E) be a vertex-colored graph, where C is the set of colors used to color V. The Graph Motif (or GM) problem takes as input G, a multiset M of colors built from C, and asks whether there is a subset S subseteq V such that (i) G[S] is connected and (ii) the multiset of colors obtained from S equals M. The Colorful Graph Motif problem (or CGM) is a constrained version of GM in which M=C, and the List-Colored Graph Motif problem (or LGM) is the extension of GM in which each vertex v of V may choose its color from a list L(v) of colors.

We study the three problems GM, CGM and LGM, parameterized by l:=|V|-|M|. In particular, for general graphs, we show that, assuming the strong exponential-time hypothesis, CGM has no (2-epsilon)^l * |V|^{O(1)}-time algorithm, which implies that a previous algorithm, running in O(2^l\cdot |E|) time is optimal. We also prove that LGM is W[1]-hard even if we restrict ourselves to lists of at most two colors. If we constrain the input graph to be a tree, then we show that, in contrast to CGM, GM can be solved in O(4^l *|V|) time but admits no polynomial kernel, while CGM can be solved in O(sqrt{2}^l + |V|) time and admits a polynomial kernel.

### BibTeX - Entry

@InProceedings{fertin_et_al:LIPIcs:2016:6083,
author =	{Guillaume Fertin and Christian Komusiewicz},
title =	{{Graph Motif Problems Parameterized by Dual}},
booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
pages =	{7:1--7:12},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-012-5},
ISSN =	{1868-8969},
year =	{2016},
volume =	{54},
editor =	{Roberto Grossi and Moshe Lewenstein},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},