# Which graph partitioning algorithm can solve this problem?

In brief:
Here I have a cyclic graph above. I want to partition the graph vertices into 3 clusters. (With the mindset of cluster-wise "load balancing")
Constraint: All the vertices in each cluster should be directly connected.
Goal: the deviance of the cluster-sums should be as small as possible. (In other words, the sum of loads of all clusters should be as balanced as possible.)

Examples:
An infeasible example: ADG CE BF. Reason: The vertices are not directly connected within each cluster.
A feasible but bad example: AB CD EFG. Reason: The load is not optimally balanced (Difference 14 14 59 is too large).
The optimal solution: ABCD EF G. Reason: the difference among three cluster-sums (28 29 30 respectively) is the smallest.

Which algorithm can get the optimal solution?

Your problem is $$\text{NP}$$-hard. To see why, consider the version of the 3-Partition problem where we're given multiset $$X = \{ x_1, x_2, \ldots, x_{3n}\}$$ of $$3n$$ nonnegative integers, and we need to decide whether $$X$$ can be partitioned into three disjoint multisets with the same sum each. Clearly, an instance $$X = \{ x_1, x_2, \ldots, x_{3n}\}$$ of the 3-Partition problem can be translated in polynomial time into a complete graph $$G = \langle V, E \rangle$$, where $$V = \{ v_i\}_{i\in [3n]}$$ and for each $$v_i$$, we have that the weight $$w(v_i) = x_i$$. That is, we view the integers as $$3n$$ vertices, and every two vertices are connected with an edge. Obviously, a balanced 3-clustering of $$G$$ corresponds to an appropriate 3-partition of the multiset $$X$$.