Motif search for large graphs
Petteri Kaski (Aalto University)
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 agrees with M. From a theory perspective the graph motif problem is known to occupy a somewhat curious position. Namely it is (i) NP-complete, but (ii) admits algorithms whose worst-case running time scales linearly in the number of edges in H (and exponentially in the size of M). Thus, as long as M remains small, there are no theoretical obstacles that would prevent scaling to large graphs. This talk reviews one possible algebraic design framework for such linear-time algorithms, constrained multilinear sieving, and presents some empirical evidence that such designs are viable in practice.
Joint work with Andreas Björklund, Łukasz Kowalik, and Juho Lauri.
Aalto Stochastics & Statistics Seminar
Mon 20 Oct 2014, 16:15
Lecture Hall M2, Otakaari 1, Espoo