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, 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-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.