2020/01/06 by István Miklós, Miklos, Istvan, Miklós Krész +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2001.01493
openalex publication_date 2020/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Here we prove that counting maximum matchings in planar, bipartite graphs is #P-complete. This is somewhat surprising in the light that the number of perfect matchings in planar graphs can be computed in polynomial time. We also prove that counting non-necessarily perfect matchings in planar graphs is already #P-complete if the problem is restricted to bipartite graphs. So far hardness was proved only for general, non-necessarily bipartite graphs.