2
$\begingroup$

Counting perfect matchings in bipartite graphs is $\# P$ complete. Let $G(V,E)$ be a graph known to have $d$ number of perfect matchings. Bipartite it the obvious way by adding $E$ vertices with one vertex splitting each edge.

Is counting the number of perfect matchings in the new graph $\# P$ complete?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Usually new graph have unequal parts $\endgroup$
    – Fedor Petrov
    Commented Jun 3, 2023 at 6:10
  • 1
    $\begingroup$ Per Fedor, if the subdivided graph has a perfect matching then every component has a unique cycle. For such graphs computing the number of perfect matchings can be done in linear time. Alternatively, subdivide each edge of $G$ with two new vertices. Now the number of perfect matchings is the same as for $G$. $\endgroup$
    – Brendan McKay
    Commented Jun 3, 2023 at 8:49
  • $\begingroup$ @BrendanMcKay Can you explain the linear time algorithm? $\endgroup$
    – Turbo
    Commented Jun 3, 2023 at 15:28
  • 1
    $\begingroup$ Consider one component, which consists of a cycle with trees attached to each vertex. A leaf edge must be in the p.m., so repeatedly remove leaf edges and both their vertices. If an isolated vertex occurs, the count is 0. Otherwise it will end when there is nothing left or just the cycle left. If nothing is left the count is 1, if an odd cycle 0, even cycle 2. Multiply the counts for each component. It's obviously polynomial. To achieve linear time, it needs a good data structure to keep track as the leaf edges are removed. $\endgroup$
    – Brendan McKay
    Commented Jun 5, 2023 at 1:40

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .