Graph Theory: Splitting a Graph?

The special case where x = n - x is called the minimum bisection problem and is NP-hard. This makes your problem NP-hard as well. There are several heuristics described in the Wikipedia article on graph partitioning including local search (e.g. , start with a random cut and repeatedly swap pairs of vertices that decrease the size of the cut) and spectral methods (e.g. , compute and threshold the second eigenvector).

If n is small, integer programming is also a possibility.

Perhaps a depth first search over nodes. We assign nodes one at a time and count the number of cuts so far. If that number exceeds the best solution's number, then we abort this one and backtrack.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.