Counting thin subgraphs via packings faster than meet-in-the-middle time

Andreas Björklund, Petteri Kaski, Łukasz Kowalik

Vassilevska and Williams (STOC 2009) showed how to count simple paths on $k$ vertices and matchings on $k/2$ edges in an $n$-vertex graph in time $n^{k/2+O(1)}$. In the same year,…