I have this problem, and I am not sure whether it is known.
Given a bipartite graph $G(U, V, E)$.
Define two sets $V_{e}, V_{o} \subseteq V$ such that $V_{e}$ and $V_{o}$ are disjoint.
Now, define another set $C \subseteq U$.
For $v \in V$, let $\Gamma(v)$ be the number of vertices in $C$ adjacent to $v$. Here is the problem:
- Find $C$ such that $\Gamma(v)$ is odd for all $v \in V_{o}$ and $\Gamma(v)$ is even for all $v \in V_{e}$.
- Can you find the smallest $C$ (The $C$ with the smallest cardinality).
Does anybody know if this problem is a version of another known problem or how to reduce it to another problem?
There is the following natural algebraic reformulation of your problem. Let $F=\{0,1\}$ be the two-element field. Put $L=F^U$. Then $L$ is the linear space over $F$.
For each $C\subset U$ let $\overline C\in F^U$ be the characteristic function of the set $C$, that is for each $u\in U$ the $u$-th component of $\bar C$ equals $1$, if $u\in C$, and equals $0$, otherwise. Then the correspondence $C\mapsto \overline C$ is the bijection between the family of all subsets of the set $U$ and the set $F^U$.
For each $v\in V$ let $N(v)$ be the neighborhood of $v$ and $\overline v=\overline{N(v)}$. Then the subset $C$ of $U$ satisfies Condition 1 of the problem iff $(\overline C,\overline v)=0$ for each $v\in V_e$ and $(\overline C,\overline v)=1$ for each $v\in V_o$. The latter condition is a system of linear equations over the field $F$. Similarly to the case of the field of the real numbers, the system has a solution iff the respective matrices have equal ranks.