I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from standard min, max cut problems. I have searched for a suitable algorithm for several days but with no success. Maybe someone can give a suggestion or at least come up with a standard name for such problem?
The problem is as follows:
Input: Undirected graph $V$ with vertex weights $u_i$ and edge weights $w_{ij}$.
Output: Graph partition in two components $S_1$ and $S_2$ to minimize the following:
$$\max((\sum_{i\in S_1}u_i-\sum_{i,j\in S_1}w_{ij}), (\sum_{i\in V-S_1}u_i-\sum_{i,j\in V-S_1}w_{ij})) $$
Basically, if we define $weight$ of a component as the sum of weights of its vertices minus the sum of weights of its edges, then I would like to find a pair of components such that a maximal weight out of the two components is minimal over all possible pairs. The edges between two components are removed.
Here is an example of possible graph partition (there may be several). The numbers mean the weights:
Thanks in advance for suggestions!
