0
$\begingroup$

Given a bipartite graph, how can one count maximum matchings with distinct subsets of vertices within one part?

For example, let us say we have a bipartite graph with parts $U$: {0, 1, 2} and $S$: {{0, 1}, {0, 1, 2}} shown below (apologies for not being able to map these more accurately, "U0" represents "0", and "S0" represents "{0, 1}" etc:

enter image description here

The maximum matchings for this graph are displayed below: enter image description here enter image description here

Now, we can see that the left part vertices in the 1st and 3rd matchings are the elements $U0$ and $U1$. Since they form an unordered pair, I would like to count just one of the 1st and 3rd matchings and not both of them.

For reference, in terms of systems of distinct representatives, the 1st maximum matching here would correspond to an SDR of {0, 1} and the 3rd maximum matching would correspond to an SDR of {1, 0}.

$\endgroup$
4
  • $\begingroup$ Thank you @Math1000 $\endgroup$ Jan 30 '20 at 15:04
  • $\begingroup$ Are you looking for an algorithm? $\endgroup$ Jan 30 '20 at 17:46
  • $\begingroup$ I'm looking for anything to be honest. $\endgroup$ Jan 30 '20 at 17:47
  • $\begingroup$ @TheHolyJoker Updated the question. I understand that it's not particularly formal, and I would struggle to define it formally given my lack of a background in math. However, I have been quite graphical. Please make any edits as you see fit, if you wouldn't mind $\endgroup$ Jan 31 '20 at 16:25
0
$\begingroup$

I'm not sure what do you mean.


One theorem that can be used to prove the existence of a solution is Hall theorem.

For finding a solution you could use Hopcroft–Karp algorithm.

For $2$-approximation, (easiest to understand and implement) one can use a greedy algorithm - just add edges as long as you can.
citation to it being $2$-approximation.


You didn't even say if you are looking at a specific graph or a family of graphs.

What are the properties of the graph?
Are they dense? (have a lot of edges) or sparse?

$\endgroup$
9
  • $\begingroup$ Hi TheHolyJoker, I edited my question to ask for a count of all the maximum matchings where the left part vertices in the matching are distinct for each maximum matching. Should I define this more rigoursly or do you understand me? $\endgroup$ Jan 30 '20 at 19:14
  • $\begingroup$ This is a completely different question, and in general it is #P-complete, as counting problems might be. This basically means we don't know how to solve those problems efficiently. This is all in the Wikipedia page of perfect matching $\endgroup$ Jan 30 '20 at 20:06
  • $\begingroup$ Hmm, yeah I'm looking for closed forms. For instance, for two sets the formula is $|A||B| - \sum_{i=1}^{|AnB|} i$ $\endgroup$ Jan 31 '20 at 2:20
  • $\begingroup$ Are you talking about the complete bipartite graph? $\endgroup$ Jan 31 '20 at 7:27
  • 1
    $\begingroup$ Okay thanks TheHolyJoker, I'll let you know when I've updated the question. $\endgroup$ Jan 31 '20 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.