Show simple item record

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

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBonnet, Édouard
HAL ID: 171728
ORCID: 0000-0002-1653-5822		*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258		*
dc.date.accessioned2016-07-20T12:46:24Z
dc.date.available2016-07-20T12:46:24Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15662
dc.language.isoenen
dc.subjectGraph Motifen
dc.subjectFPTen
dc.subjectParameterized Complexityen
dc.subjectStructural Parametersen
dc.subjectComputational Biologyen
dc.subject.ddc003en
dc.titleThe Graph Motif Problem Parameterized by the Structure of the Input Graphen
dc.typeCommunication / Conférence
dc.description.abstractenThe 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.en
dc.identifier.citationpages319--330en
dc.relation.ispartoftitle10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Proceedingsen
dc.relation.ispartofeditorHusfeldt, Thore
dc.relation.ispartofeditorKanj, Iyad
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum für Informatiken
dc.relation.ispartofpublcityWadernen
dc.relation.ispartofdate2015
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-939897-92-7en
dc.relation.conftitle10th International Symposium on Parameterized and Exact Computation (IPEC 2015)en
dc.relation.confdate2015-09
dc.relation.confcityPatrasen
dc.relation.confcountryGreeceen
dc.relation.forthcomingnonen
dc.identifier.doi10.4230/LIPIcs.IPEC.2015.319en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2016-07-18T11:18:38Z
hal.faultCode{"duplicate-entry":{"hal-01505505":{"doi":"1.0"}}}
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
30.pdf
Size:
567.2Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record