Abstract
In the Graph Motif problem, we are given as input a vertex-colored graph $H$ (the host graph) and a multiset of colors $M$ (the motif). Our task is to decide whether $H$ has a connected set of vertices whose multiset of colors exactly agrees with $M$.
The worst-case time complexity of the Graph Motif problem is well-understood in a fairly tight sense:
1. Assuming that the host graph has $m$ edges and that the motif has size $k$, there exists a randomized algorithm that solves the problem in time $O(2^k k^2 (log k)^2 m)$.
2. Unless there is a breakthrough in the time complexity of the Set Cover problem, the Graph Motif problem does not admit an algorithm that runs in time $O^*((2-\epsilon)^k)$ for any constant $\epsilon>0$.
This talk reviews theory and engineering effort that resulted in an open-source algorithm implementation that scales in practice (as long as $k$ remains small) to graphs with hundreds of millions of edges on a single compute node.
Joint work with Andreas Björklund, Łukasz Kowalik, and Juho Lauri.