Graph partition optimization with weights on edges and vertices I am interesting in studying the complexity of some graph partition problems, where it is important to take into account the weights on the edges as well as the weight on the vertices. Max-cut only cares about the weights on the edges, while other problems only care about the weights on the vertices. Does anyone know problems in which BOTH weights are important in order to make the optimal partition?

Thank you very much

Here's an example problem: 

Input: directed graph with vertex weights $u_i$ and arcs weights $w_{ij}$.

Output: a subset S of V to maximize the sum of the following things:


$\sum_{i, j \in S} w_{ij} + \sum_{i,j \in V - S} w_{ij}$ (arc weights inside each side)
$\sum_{|{i,j} \cap S| = 1} w_{ij}u_j$: the sum over all cut edges of product of  arc weight and the weight of the destination vertex.
(not quite an answer, but too long for a comment)

Given your new cost function, I'm wondering if there's a simpler formulatio. Let $W = \sum_{(i,j) \in E} w_{ij}$. Now your goal is to maximize

\[ W - \sum_{|\{i,j\} \cap S| = 1} w_{ij} + \sum_{|\{i,j\} \cap S| = 1} w_{ij}u_j\]

Collecting terms, your goal is then to minimize

\[ \sum_{|\{i,j\} \cap S| = 1} w_{ij} (u_j - 1)\]

Setting $w&#39;_{ij} = w_{ij}(u_j - 1)$, your problem now becomes a min cut problem with the twist that it's not a typical min cut (you're not counting edges going from one side to the other, but both sides)