Counting perfect matchings #P-hard for α=2 graphs
Conjecture 3 · arXiv:2202.11988
Status solved high confidence
Conjecture 3 from arXiv:2202.11988, asserting that counting perfect matchings in graphs of independence number at most 2 is #P-complete, was resolved by El Maalouly and Wang in arXiv:2210.15014 (October 2022). Their paper proves #P-completeness for both general graphs with independence number ≤ 2 and bipartite graphs with bipartite independence number ≤ 2, via reductions from counting perfect matchings in bipartite graphs using graph-theoretic constructions.
Cited literature (1)
-
Proves that counting perfect matchings is #P-complete when restricted to graphs with independence number at most 2 (and bipartite graphs with bipartite independence number at most 2), directly resolving the conjecture.
Reviewer notes. The conjecture was resolved by a follow-up paper by one of the original authors (El Maalouly) together with Wang, submitted approximately three months after the conjecture paper's final arXiv revision. Both papers are from 2022.
Context
The authors note that for all previously known graph classes on which EM is tractable (planar graphs, $K_{3,3}$-minor-free graphs, complete and complete bipartite graphs), counting perfect matchings is also polynomial. Their new results for graphs of independence number 2 break this alignment, since no polynomial counting scheme is known for this class and the authors believe counting is hard.
Notes. The paper text is truncated before Section 6 (open problems), so additional open problems stated there could not be extracted.
Source paper
Exact Matching in Graphs of Bounded Independence Number
Nicolas El Maalouly, Raphael Steiner · 2022-07-13
https://arxiv.org/abs/2202.11988
PDF source