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:
The maximum matchings for this graph are displayed below:
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}.
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?