2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\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.