The Simple, Little and Slow Things Count: On Parameterized Counting Complexity

We consider some of the most recent refinements to classical counting complexity, namely, the parameterized complexity and the exponential-time complexity of counting problems.

In parameterized complexity, problem instances come together with a parameter k, and this allows for a more fine-grained complexity analysis than could be achieved by considering only the input size n. (For example, in the setting of graphs, possible parameters could be the maximum degree, genus or certain width-measures of the graph.) We will survey various parameterizations of the permanent, together with lower bounds under the exponential-time hypotheses ETH and SETH. These hypotheses postulate lower bounds on the running time for deciding satisfiability of CNF-formulas and have been recently used to explain the lack of progress in many fundamental algorithmic questions.

We also consider the problems of counting general subgraphs H in a host graph G, parameterized by the size of H. This gives rise to the problems #Sub(C) for fixed graph classes C: For inputs H and G, where H is from C, we wish to count H-copies in G. We show a dichotomy theorem that, depending on C, establishes #Sub(C) to be either polynomial-time solvable or complete for #W[1], the parameterized analog of #P.