Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time

摘要

Vassilevska and Williams (STOC'09) showed how to count simple paths on k vertices and matchings on k/2 edges in ann-vertex graph in time n(k/2+O(1)). In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP'09), and Bjorklund et al. (ESA'09), via n(st/2+O(1))-time algorithms for counting t-tuples of pairwise disjoint sets drawn from a given family of s-sized subsets of an n-element universe. Shortly afterwards, Alon and Gutner (TALG'10) showed that these problems have Omega(n(left perpendicular st/2 left perpendicular)) and Omega(n(left perpendicular k/2 left perpendicular)) lower bounds when counting by color coding.