# Partitioning a graph with specific constraints

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.

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.