Show simple item record

dc.contributor.authorBonnet, Édouard
dc.contributor.authorSikora, Florian
dc.date.accessioned2019-03-22T08:35:25Z
dc.date.available2019-03-22T08:35:25Z
dc.date.issued2017
dc.identifier.issn0166-218X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18546
dc.language.isoenen
dc.subjectParameterized complexityen
dc.subjectGraph motif problemen
dc.subjectStructural parameterizationen
dc.subjectComputational biologyen
dc.subject.ddc511en
dc.titleThe Graph Motif problem parameterized by the structure of the input graphen
dc.typeArticle accepté pour publication ou publié
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 mostly 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. In the many utilizations of Graph Motif, however, the input graph originates from real-life applications 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. For the FPT cases, we also give some kernelization lower bounds as well as some ETH-based lower bounds on the worst case running time. 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.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol231en
dc.relation.isversionofjnldate2017-11
dc.relation.isversionofjnlpages78-94en
dc.relation.isversionofdoi10.1016/j.dam.2016.11.016en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-03-22T08:31:33Z
hal.person.labIds220549
hal.person.labIds989
hal.identifierhal-02076324*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record