QLunch: Radu Curticapean

Speaker: Radu Curticapean, IT University of Copenhagen, Denmark, radu.curticapean@gmail.com

Joint work with Mingji Xia, Chinese Academy of Sciences, China, mingji@ios.ac.cn

Title: Parameterizing the Permanent: Hardness for Fixed Excluded Minors

Abstract: In the 1960s, statistical physicists discovered a fascinating algorithm for counting perfect matchings in planar graphs. Valiant later showed that the same problem is #P-hard for general graphs. Since then, the algorithm for planar graphs was extended to bounded-genus graphs, to graphs excluding K_{3,3} or K_5 as a minor, and more generally, to any graph class excluding a fixed minor H that can be drawn in the plane with a single crossing. This stirred up hopes that counting perfect matchings might be polynomial-time solvable for graph classes excluding any fixed minor H. Alas, in this talk, we show #P-hardness for K_8-minor-free graphs by a simple and self-contained argument.