| Maximum Motif Problem in Vertex-Colored Graphs (2009) | |||||||||||||||
Abstract | |||||||||||||||
| Searching for motifs in graphs has become a crucial problem in the analysis of biological networks. In this context, dierent graph motif problems have been considered [12, 6, 4]. Pursuing a line of research pioneered by Lacroix et al. [12], we introduce in this paper a new graph motif problem: given a vertex colored graph G and a motif M, where a motif is a multiset of colors, nd a maximum cardinality submotif M' included in M that occurs as a connected motif in G. We prove that the problem is APX-hard even in the case where the target graph is a tree of maximum degree 3, the motif is actually a set and each color occurs at most twice in the tree. We complement these results by presenting two fixed-parameter algorithms for the problem, where the parameter is the size of the solution. Finally, we give exact efficient exponential-time algorithms for the problem. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||