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.IPEC.2015.319
URN: urn:nbn:de:0030-drops-55937
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5593/
Go to the corresponding LIPIcs Volume Portal

Bonnet, Édouard ; Sikora, Florian

The Graph Motif Problem Parameterized by the Structure of the Input Graph

pdf-format:
30.pdf (0.6 MB)

Abstract

The Graph Motif problem was introduced in 2006 in the context of biological networks. It consists of deciding whether or not a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Graph Motif has been analyzed from the standpoint of parameterized complexity. The main parameters which came into consideration were the size of the multiset and the number of colors. Though, in the many applications of Graph Motif, the input graph originates from real-life and has structure. Motivated by this prosaic observation, we systematically study its complexity relatively to graph structural parameters. For a wide range of parameters, we give new or improved FPT algorithms, or show that the problem remains intractable. Interestingly, we establish that Graph Motif is W[1]-hard (while in W[P]) for parameter max leaf number, which is, to the best of our knowledge, the first problem to behave this way.

BibTeX - Entry

@InProceedings{bonnet_et_al:LIPIcs:2015:5593,
  author =	{{\'E}douard Bonnet and Florian Sikora},
  title =	{{The Graph Motif Problem Parameterized by the Structure of the Input Graph}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{319--330},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5593},
  URN =		{urn:nbn:de:0030-drops-55937},
  doi =		{10.4230/LIPIcs.IPEC.2015.319},
  annote =	{Keywords: Parameterized Complexity, Structural Parameters, Graph Motif, Computational Biology}
}

Keywords: Parameterized Complexity, Structural Parameters, Graph Motif, Computational Biology
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

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