Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect matching.
I believe that this problem is at least #P-hard, but I can't find anything that states such.
I've found a similar question on cstheory which states that counting subsets of vertices on a general graph for which there is an induced perfect matching is #P-Complete. The difference between our questions is I consider $U^\prime$ unique whereas they consider $U^\prime \sqcup V^\prime$ unique.
An alternative expression of my question could be: count $U^\prime \subseteq U$ for which the induced subgraph $G[U^\prime \sqcup V]$ contains a (maximum, potentially imperfect) matching $M$ where $\lvert M \rvert = \lvert U^\prime \rvert$, i.e. every $u^\prime \in U^\prime$ is adjacent to some $m \in M$.
