Large Structures Seminar: Petteri Kaski

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.