Determine total amount of matching combinations (1:1) in a maximum node graph

Question

Is there a "non-bruteforce" way to determine the total amount of matching combinations (1:1) between a set of nodes with corresponding edges?

Every node can only be connected to a single other node.

Say I have a dataset like this:

• Node 1

  • Edge to 2, 3 and 5

• Node 2

  • Edge to 1, and 3

• Node 3

  • Edge to 1 and 4

• Node 4

  • Edge to 3 and 5

• Node 5

  • Edge to 1 and 4

This particular set has a maximum of two matches for each combination, as every node can only be connected to one other node.

This particular dataset has a total of 6 maximum combinations in a maximum matching result (Where every node, that can be matched is matched)

Attempting to count larger datasets with more edges relating the nodes easily gets very difficult, which is why I'm wondering if there is a better way (other than bruteforcing) to calculate the total amount of combinations.

Answer 1

Counting the number of matchings, or the number of maximum matchings, are both #P-complete (see here).

#P-completeness is kind-of analogous to NP-completeness, but for counting problems. That essentially means that, unfortunately, there is no better way than bruteforcing.