Large Structures Seminar: Petteri Kaski

The (symbolic) Laplacian matrix of a graph G is a rich source of algebraic combinatorics. Our interest is on directed graphs, where by puncturing the Laplacian at a vertex r and taking the determinant, we obtain, by the classical (directed) Matrix–Tree Theorem, a symbolic generating function for the spanning out-branchings of G rooted at r. In this talk we seek to understand Laplacian determinants via the algebraic combinatorics of “incidence assignments” that we can then turn into new randomized algorithm designs for, e.g., the Hamiltonian cycle problem on directed graphs.

We present two such algorithm designs. First, for any constant 0 < \lambda < 1 and any prime p, we present a randomized algorithm that, given an n-vertex directed graph G as input, counts the number of Hamiltonian cycles modulo p^{\lfloor(1-\lambda)n/(3p)\rfloor} in expected time c^n for a constant c<2 that depends only on p and \lambda. Second, we present a randomized algorithm that with a negligible probability of a false negative detects a directed Hamiltonian cycle in a given n-vertex directed graph G in time O*(3^{n-\alpha(G)}) and space polynomial in n, where \alpha(G) is the size of a maximum independent set in G.

This is joint work with Andreas Björklund (Lund University) and Ioannis Koutis (University of Puerto Rico).