Counting Perfect Matchings in Dense Graphs Is Hard

10/26/2022
by   Nicolas El Maalouly, et al.
0

We show that the problem of counting perfect matchings remains #P-complete even if we restrict the input to very dense graphs, proving the conjecture in [5]. Here "dense graphs" refer to bipartite graphs of bipartite independence number ≤ 2, or general graphs of independence number ≤ 2. Our proof is by reduction from counting perfect matchings in bipartite graphs, via elementary linear algebra tricks and graph constructions.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset