Graph partition optimization with weights on edges and vertices

Question

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:

1. $\sum_{i, j \in S} w_{ij} + \sum_{i,j \in V - S} w_{ij}$ (arc weights inside each side)

2. $\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.

Answer 1

(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'_{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)

Answer 2

I think Sparsest cut or edge expansion, is good enough for you, because deals with both edges and nodes. The task is to find a cut, with $S\subset V$, $|S|\leq {|V|\over2}$ in one part such that:

$$\alpha(G) = \min \{ {E(S,S^c)\over |S|}\}$$

is minimized over all possible set of $S$.

You may look at Sparsest cut and bottlenecks in graphs by Matula,Shahrokhi for proof of NP-Hardness (proof is by using max cut).

Also P. Bonsmaa et al, shown that it's NP-Hard even in uniform case (means all edges are of weight $1$).