Consider the following problem: let $(U \cup V, E)$ be a bipartite graph. Is it possible to label the vertices of $U$ with either $``+"$ or $``-"$ such that every vertex of $V$ is adjacent to a vertex labeled $+$ and a vertex labeled $-$?
This seems like a pretty natural problem, and I would be surprised if it hasn't been considered before. I'm not asking for someone to come up with an algorithm for this (although that would be great). Does this problem have a name?
Obvious it can be reduced to an integer linear program, which might be efficient in practice.