License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2016.7
URN: urn:nbn:de:0030-drops-60837
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6083/
Go to the corresponding LIPIcs Volume Portal

Fertin, Guillaume ; Komusiewicz, Christian

Graph Motif Problems Parameterized by Dual

pdf-format:
LIPIcs-CPM-2016-7.pdf (0.5 MB)

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},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6083},
  URN =		{urn:nbn:de:0030-drops-60837},
  doi =		{10.4230/LIPIcs.CPM.2016.7},
  annote =	{Keywords: NP-hard problem, subgraph problem, fixed-parameter algorithm, lowerbounds, kernelization}
}

Keywords: NP-hard problem, subgraph problem, fixed-parameter algorithm, lowerbounds, kernelization
Collection: 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Issue Date: 2016
Date of publication: 27.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI