# Graph partition with weighted vertices and edges

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!

• Your problem is NP-hard. Hint: reduce from Partition to the special case of your problem with $w_{ij}=0$. Apr 4, 2016 at 18:40
• @NealYoung do you mean to prove NP-hardness by reducing to the special case? That's true, I agree. But I hoped for some heuristic algorithm or at least something better than brute force... Apr 4, 2016 at 18:58
• Yes. As for heuristics, maybe integer linear programming? (You can modify the reduction above to show that deciding whether there is solution of cost zero is NP-hard, so, unless P=NP, there is no poly-time algorithm with multiplicative-approximation guarantee.) Apr 4, 2016 at 21:43