3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Isn't this basically the same as (well, more general than) your previous question: mathoverflow.net/questions/443258/… ? $\endgroup$
    – Sam Hopkins
    Commented May 30, 2023 at 20:01
  • $\begingroup$ Sorry, I understand now that this question is about going in the opposite direction, compared to your last question: from total matchings to perfect matchings. $\endgroup$
    – Sam Hopkins
    Commented May 30, 2023 at 20:08
  • $\begingroup$ @SamHopkins Right, these are related questions - I was hoping perhaps maybe there was some complexity theory distinction. So finding a matching is trivial; take no edges. But finding a perfect matching is harder (but can be done in polynomial time, e.g. cs.stackexchange.com/questions/62526/… ) so finding G' from G in polynomial time is still ok. $\endgroup$
    – Per Alexandersson
    Commented May 31, 2023 at 5:08
  • 1
    $\begingroup$ Definitions? Please. $\endgroup$
    – Wlod AA
    Commented May 31, 2023 at 6:23

0

Reset to default

You must log in to answer this question.