Computer Science – Computational Complexity
Scientific paper
2010-02-09
Computer Science
Computational Complexity
Conference version in International Symposium on Mathematical Foundations of Computer Science (MFCS), Brno : Czech Republic (2
Scientific paper
10.1007/s00453-011-9600-8
The problems studied in this article originate from the Graph Motif problem introduced by Lacroix et al. in the context of biological networks. The problem is to decide if a vertex-colored graph has a connected subgraph whose colors equal a given multiset of colors $M$. It is a graph pattern-matching problem variant, where the structure of the occurrence of the pattern is not of interest but the only requirement is the connectedness. Using an algebraic framework recently introduced by Koutis et al., we obtain new FPT algorithms for Graph Motif and variants, with improved running times. We also obtain results on the counting versions of this problem, proving that the counting problem is FPT if M is a set, but becomes W[1]-hard if M is a multiset with two colors. Finally, we present an experimental evaluation of this approach on real datasets, showing that its performance compares favorably with existing software.
Guillemot Sylvain
Sikora Florian
No associations
LandOfFree
Finding and counting vertex-colored subtrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Finding and counting vertex-colored subtrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding and counting vertex-colored subtrees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-124822