| Weak pattern matching in colored graphs: Minimizing the number of connected components (2008) | |||||||||||||||
Abstract | |||||||||||||||
| In the context of metabolic network analysis, Lacroix et al. 11 introduced the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors and an occurrence of a motif is a subset of connected vertices which are colored by all colors of the motif. We consider in this paper the above-mentioned problem in one of its natural optimization forms, referred hereafter as the Min-CC problem: Find an occurrence of a motif in a vertexcolored graph, called the target graph, that induces a minimum number of connected components. Our results can be summarized as follows. We prove the Min-CC problem to be APX–hard even in the extremal case where the motif is a set and the target graph is a path. We complement this result by giving a polynomial-time algorithm in case the motif is built upon a fixed number of colors and the target graph is a path. Also, extending recent research 8, we prove the Min-CC problem to be fixed-parameter tractable when parameterized by the size of the motif, and we give a faster algorithm in case the target graph is a tree. Furthermore, we prove the Min-CC problem for trees not to be approximable within ratio c log n for some constant c> 0, where n is the order of the target graph, and to be W[2]–hard when parameterized by the number of connected components in the occurrence of the motif. Finally, we give an exact efficient exponential-time algorithm for the Min-CC problem in case the target graph is a tree. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||