•  
  •  
 
Tsinghua Science and Technology

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.

Publisher

Tsinghua University Press

Share

COinS