[Solved]: Proving NP-hardness of strange graph partition problem

Let’s reduce multiway cuts problem, a variant of minimum $k$-cut, to your problem. In particular, consider the minimum 3-way cut problem, which is NP-hard for all edge weight equal to 1 (see The complexity of multiway cuts). A (minimum) 3-way cut problem is: given a graph $G = (V,E)$ and terminals $s_1,s_2,s_3in V$, find a minimum set of edges $E’subseteq E$ such that the removal of $E’$ from $E$ disconnects each terminal $s_i$ from the others. Its decision version is to find out if it’s possible to disconnect $s_1,s_2,s_3$ by removing no more than $w$ edges, where $w$ is a part of the input. Given graph $G$, terminals $s_1,s_2,s_3$ and integer $w$, we would like to reduce the 3-way cut problem to your “strange graph partition problem”. For each terminal $s_i$, we add $N$ more verteces to be its neighbors. As hinted by its name, $N$ would be a sufficiently large number. The weight of all verteces are 0 except for $s_1,s_2,s_3$, whose weights are $1,10,100$ resp. Denote this new graph by $G’$. It’s obvious that $s_1,s_2,s_3$ can be disconnected by removing $w$ edges in $G$ if and only if they can be disconnected by removing $w$ edges in $G’$. If a partition $G’_p$ of $G’$ disconnects $s_1,s_2,s_3$, its score is roughly $10101/N$, or more precisely, no less than $$frac{10101}{N+n}$$ as the part containing $s_i$ has no more than $N+n$ verteces, where $n$ is the number of verteces in $G$. On the other hand, if a partition $G’_p$ fails to disconnect $s_1,s_2,s_3$, its score is no more than $$frac{10060.5}{N-w}$$. When $N$ is sufficiently large, $frac{10101}{N+n} > frac{10060.5}{N-w}$, so $G$ can be 3-way partitioned by removing $w$ edges if and only if $G’$ has a partition removing $w$ edges, whose score is at least $frac{10101}{N+n}$.