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 muchHere'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. 
Graph partition optimization with weights on edges and vertices
cc.complexity theory;graph theory