parameterized complexity, counting problems, dichotomy theorems
Parameterized complexity is a multivariate theory for the analysis of computational problems. It leads to practically efficient algorithms for many ����-hard problems and also provides a much finer complexity classification for other intractable problems. Although the theory is mostly on decision problems, parameterized complexity naturally extends to counting problems as well. The purpose of this article is to survey a few aspects of parameterized counting complexity, with a particular emphasis on some general frameworks in which parameterized complexity proves to be indispensable.
Tsinghua University Press
Chihao Zhang, Yijia Chen. Counting Problems in Parameterized Complexity. Tsinghua Science and Technology 2014, 19(04): 410-420.