Finding and counting vertex-colored subtrees

Abstract

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.

Conference version in International Symposium on Mathematical Foundations of Computer Science (MFCS), Brno : Czech Republic (2010) Journal Version in Algorithmica

References in corpus (1)

• Finding paths of length k in O*(2^k) time

Cited by in corpus (6)

• A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets
• Constrained multilinear detection for faster functional motif discovery
• The Graph Motif problem parameterized by the structure of the input graph
• Some results on more flexible versions of Graph Motif
• On motifs in colored graphs
• Representative Sets of Product Families