1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Your problem is known as hypergraph 2-colorability; the hypergraph has $U$ as vertices and the neighborhoods of vertices of $V$ as edges. Determining whether a hypergraph is 2-colorable is NP-complete.

| cite | improve this answer | |
$\endgroup$

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.