Sub-Exponential Time Lower Bounds for #VC and #Matching on 3-Regular Graphs

This article focuses on the sub-exponential time lower bounds for two canonical #P -hard problems: counting the vertex covers of a given graph (#VC) and counting the matchings of a given graph (#Matching), under the well-known counting exponential time hypothesis (#ETH). Interpolation is an essential method to build reductions in this article and in the literature. We use the idea of block interpolation to prove that both #VC and #Matching have no 2(o(N)) time deterministic algorithm, even if the given graph with N vertices is a 3-regular graph. However, when it comes to proving the lower bounds for #VC and #Matching on planar graphs, both block interpolation and polynomial interpolation do not work. We prove that, for any integer N > 0, we can simulate N pairwise linearly independent unary functions by gadgets with only O(log N) size in the context of #VC and #Matching. Then we use log-size gadgets in the polynomial interpolation Nto prove that planar #VC and planar #Matching have no 2(o(root logN)) time deterministic algorithm. The lower bounds hold even if the given graph with N vertices is a 3 -regular graph. Based on a stronger hypothesis, randomized exponential time hypothesis (rETH), we can avoid using interpolation. We prove that if rETH holds, both planar #VC and planar #Matching have no 2 ('/77\1) time randomized algorithm, even that the given graph with N vertices is a planar 3-regular graph. The 2(Omega(root N)) time lower bounds are tight, since there exist 2(O(root N)) time algorithms for planar #VC and planar #Matching. We also develop a fine-grained dichotomy for a class of counting problems, symmetric Holant*.