Petteri Kaski: Constrained multilinear detection and generalized graph motifs

Many hard combinatorial problems can be reduced to the framework of detecting whether a multivariate polynomial P(x)=P(x_1,x_2,...,x_n) has a monomial with specific properties of interest. In such a setup P(x) is not available in explicit symbolic form but is implicitly defined by the problem instance at hand, and our access to P(x) is restricted to having an efficient algorithm for computing values of P(x) at points of our choosing. This talk will focus on detecting multilinear monomials with auxiliary color constraints and applications to graph motif problems parameterized by motif size.

Joint work with Andreas Björklund (Lund) and Łukasz Kowalik (Warsaw).

arxiv.org/abs/1209.1082

The speaker was invited by Per Austrin.