2026-07-22T06:37:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6083 2024-03-06T10:37:33Z ddc:004 open_access

Graph Motif Problems Parameterized by Dual Fertin, Guillaume Komusiewicz, Christian NP-hard problem subgraph problem fixed-parameter algorithm lowerbounds kernelization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guillaume Fertin and Christian Komusiewicz 2016 Is Part Of LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2016.7 urn:nbn:de:0030-drops-60837 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.7 eng https://creativecommons.org/licenses/by/3.0/legalcode