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, two different algorithms with the same runtime were given by Koutis and Williams (ICALP 2009), and Bjorklund et al. (ESA 2009), 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 2010) showed that these problems have Ω(n~(st/2c)) and Ω(n~(k/2}) lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the "meet-in-the-middle" exponent st=2 can be beaten and give an algorithm that counts in time n~(0:4547st+O(1)) for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth pk in an n-vertex graph in n~(0:4547k+2p+O(1)) time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound.
展开▼
