Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Research Seminar

Radu Curticapean: Parameterized counting complexity

April 4, 2012, 1:30 p.m.
E 1 3, Room 415

We will give an introduction into parameterized counting complexity, a natural refinement of classical counting complexity in terms of parameterized complexity. Almost all material covered in this talk can be found in "The parameterized complexity of counting problems" by Jörg Flum and Martin Grohe

In a short first part, we consider the most basic definitions, including parameterized counting reductions and the class #W[1], and close this part with two extremely handy logic-based tools for the identification of fixed-parameter tractable counting problems.

Then, we prove that counting directed/undirected cycles/paths of length k in general graphs is #W[1]-hard in the parameter k, and thus unlikely to be fixed-parameter tractable. This is interesting in view of the known fixed-parameter tractability of the corresponding existence problems.

Finally, we state some open problems and vague ideas on how these problems could be tackled.