Title: The Parameterized Complexity of Counting k-Matchings

Speaker: Radu Curticapean (Saarland University, Germany)

　　    ( www-cc.cs.uni-saarland.de/curticapean )

Time: 14:00, October 28th, 2013

Venue: Lecture Room, 3rd Floor, Building #5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

Abstract:

The study of counting problems from the perspective of computational complexity was initiated by Valiant in a seminal paper. In this paper, he introduced the complexity class #P and showed that the problem of counting perfect matchings in a given graph is #P-complete, contrasting the fact that perfect matchings can be found in polynomial time.

Counting (perfect) matchings has since stayed an important problem in this area, also because of its applications outside of computer science, such as in chemistry and statistical physics. To cope with its hardness, many variations were studied, with results including that perfect matchings can be counted in polynomial time on planar graphs, while (non-necessarily perfect) matchings are #P-hard to count, even on planar bipartite graphs of maximum degree 3. The number of matchings in a general graph is also known to admit a fully-polynomial randomized approximation scheme.

A new variation comes from parameterized counting complexity, a relatively young area that studies counting problems from the viewpoint of parameterized complexity. It is built around the notion of parameterized counting problems, which can be fixed-parameter tractable or #W[1]-hard. Flum and Grohe showed that the parameterized problem of counting simple paths with k edges is #W[1]-hard, which is particularly interesting since deciding the existence of a k-path was already known to be fixed-parameter tractable. The parameterized complexity of counting matchings with k edges however remained open and was conjectured to be #W[1]-hard.

In this talk, we present a #W[1]-hardness proof for the problem of counting matchings with k edges, thus resolving the aforementioned conjecture. The proof consists of a series of reductions that start from the #W[1]-hard problem of counting cliques of size k, and involves some algebraic arguments.

The talk is self-contained and includes an introduction to parameterized counting complexity.

Biography:

Radu Curticapean is a PhD student at Saarland University who is interested in the intersection of parameterized complexity and counting complexity theory. He is supervised by Markus Bl ser.