Parameterizing the Permanent: Hardness for K₈-minor-free graphs

2021/08/29 by Radu Curticapean, Mingji Xia, Curticapean, Radu +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.2108.12879

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₅, 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 paper, we show #P-hardness for K₈-minor-free graphs by a simple and self-contained argument.

Related

• Parameterizing the Permanent: Genus, Apices, Minors, Evaluation mod 2^k
• Excluding Single-Crossing Matching Minors in Bipartite Graphs
• Counting perfect matchings in graphs that exclude a single-crossing minor
• Finding forbidden minors in sublinear time: a n^1/2+o(1)-query\n one-sided tester for minor closed properties on bounded degree graphs
• Counting Maximum Matchings in Planar Graphs Is Hard