"Counting Problems in Parameterized Complexity" by Chihao Zhang and Yijia Chen

Home > TSINGHUA-SCIENCE-AND-TECHNOLOGY > Vol. 19 (2014) > Iss. 4

Article Title

Counting Problems in Parameterized Complexity

Authors

Chihao Zhang, Department of Computer Science and Engineering, Shanghai Jiao Tong University, No. 800 Dongchuan Road, Shanghai 200240, China.
Yijia Chen, Department of Computer Science and Engineering, Shanghai Jiao Tong University, No. 800 Dongchuan Road, Shanghai 200240, China.

Keywords

parameterized complexity, counting problems, dichotomy theorems

Abstract

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.