Holographic reduction for some counting problems

Holographic reduction is a powerful tool to divide a line between tractable cases and #P-hardness. Based on dichotomies of #CSP, Holant⁎ and Holantc problem, we succeed to give a dichotomy for some particular problems in Cai et al. (2008) [5] and Valiant (2004) [8].

► We prove #P-hardness for some counting problems.
► It is motivated by the holographic algorithm proposed by Valiant.
► As a result, we establish some dichotomies for these problems.