Skip to main content
added 199 characters in body
Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

A matching in a graph is a subset of the edges such that no two edges share a vertex. A perfect matching is a matching where every vertex is part of exactly one edge in the matching.

Counting the total number of matchings in a general graph is #P-complete (i.e. hard). Also, counting the total number of perfect matchings is also #P-complete.

We know that matchings can be translated into independence sets, so every matching counting problem can be made into a counting independence sets in a related graph. (But the converse is not true, independence sets are more general).

Question: Given a graph $G$, can we find (in some efficient manner) a graph $G'$ such that the number of matchings of $G$ is the same as the number of perfect matchings in $G'$?

Question 2: If the answer is no for general graphs, what about bipartite graphs?

Counting the total number of matchings in a general graph is #P-complete (i.e. hard). Also, counting the total number of perfect matchings is also #P-complete.

We know that matchings can be translated into independence sets, so every matching counting problem can be made into a counting independence sets in a related graph. (But the converse is not true, independence sets are more general).

Question: Given a graph $G$, can we find (in some efficient manner) a graph $G'$ such that the number of matchings of $G$ is the same as the number of perfect matchings in $G'$?

Question 2: If the answer is no for general graphs, what about bipartite graphs?

A matching in a graph is a subset of the edges such that no two edges share a vertex. A perfect matching is a matching where every vertex is part of exactly one edge in the matching.

Counting the total number of matchings in a general graph is #P-complete (i.e. hard). Also, counting the total number of perfect matchings is also #P-complete.

We know that matchings can be translated into independence sets, so every matching counting problem can be made into a counting independence sets in a related graph. (But the converse is not true, independence sets are more general).

Question: Given a graph $G$, can we find (in some efficient manner) a graph $G'$ such that the number of matchings of $G$ is the same as the number of perfect matchings in $G'$?

Question 2: If the answer is no for general graphs, what about bipartite graphs?

Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

Counting matchings and perfect matchings

Counting the total number of matchings in a general graph is #P-complete (i.e. hard). Also, counting the total number of perfect matchings is also #P-complete.

We know that matchings can be translated into independence sets, so every matching counting problem can be made into a counting independence sets in a related graph. (But the converse is not true, independence sets are more general).

Question: Given a graph $G$, can we find (in some efficient manner) a graph $G'$ such that the number of matchings of $G$ is the same as the number of perfect matchings in $G'$?

Question 2: If the answer is no for general graphs, what about bipartite graphs?