Fertin, Guillaume ;
Komusiewicz, Christian
Graph Motif Problems Parameterized by Dual
Abstract
Let G=(V,E) be a vertexcolored 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 ListColored 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:=VM. In particular, for general graphs, we show that, assuming the strong exponentialtime hypothesis, CGM has no (2epsilon)^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:17:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770125},
ISSN = {18688969},
year = {2016},
volume = {54},
editor = {Roberto Grossi and Moshe Lewenstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6083},
URN = {urn:nbn:de:0030drops60837},
doi = {10.4230/LIPIcs.CPM.2016.7},
annote = {Keywords: NPhard problem, subgraph problem, fixedparameter algorithm, lowerbounds, kernelization}
}
2016
Keywords: 

NPhard problem, subgraph problem, fixedparameter algorithm, lowerbounds, kernelization 
Seminar: 

27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

Issue date: 

2016 
Date of publication: 

2016 