We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills these constraints:
- |V1| - |V2| = 0 or 1 (V1 and V2 have the same amount of nodes or V1 contains one node more that V2)
- either
- [case A] all nodes in V1 have edges to all nodes in V2
- [case B] all nodes in V1 have no edges to any node in V2
We had a few ideas to find those partitions via divide-and-conquer involving the degrees of each node to differentiate between case A and B. If we find any node v with degree(v) < |V2| then there is a partition with case B, otherwise if we find a node v with degree(v)> |V1| then there is a partition that fulfills case A. However other than that we have been stuck and extendind or other ideas ended in a dead end.
How do we find those partitions? I'd like to not be given the answer but only a pointer to find a easy algorithm for the problem.
1 Answer 1
It suffices to be able to identify case B, since a graph satisfies case A if, and only if, its complement satisfies B.
A graph satisfies case B if, and only if, it is composed of components of size $n_1, \dots, n_\ell$ and there is some set $S\subset \{1, \dots, \ell\}$ such that $\sum_{i\in S} n_i = \sum_{j\notin S} n_j$. (If $n_1 + \dots + n_\ell$ is odd, this is impossible, so include a fake component of size 1ドル$.)
This is the set partition problem. Bad news! It's NP-complete. Good news! It's not strongly NP-complete and we're encoding the numbers $n_i$ in unary. This means that the pseudopolynomial algorithms described on the Wikipedia page are actually polynomial-time algorithms in your context. By checking the algorithms carefully, you can probably avoid the "fake component" trick.