Does the problem "partition a vertex-weighted graph into $k$ balanced connected parts" have a standard name?

Question

Consider the following problem:

Given an integer $k$ and a vertex-weighted graph $G=(V,E)$, find a partition of $V$ into $V_1,\ldots,V_k$ such that each subgraph induced by $V_i$ is connected, and such that $\max_i w(V_i)$ is minimized, where $w(V_i)$ is the total weight of the vertices in $V_i$.

It can be easily seen that this problem is NP-complete. For hardness, note that we can solve Partition by using a complete graph.

Questions: Does this problem have a standard name? Are there any papers that study this problem, or maybe slight variations of it? Is the problem still hard for sparse graphs? I am particularly interested in references that could lead to an implementation with good performance in practice.

Answer 1

The paper [Chlebikova, Approximating the maximally balanced connected partition problem in graphs, 1996] studies a related problem: They have $k=2$, and they maximize $\min(|V_1|,|V_2|)$. It should be a good place to start searching for related results, by following the citation graph.

Answer 2

If I understand corectly, it seems that the problem is NPC even if we want to devide it into two parts.

Here is a reduction from partition problem. (I didn't check it carefully hope it works).

Let say $w_1,\ldots,w_n $ form an instance of the partition problem. Take a graph with $2n$ nodes $v_1,\ldots,v_{2n}$.

Assign weight $w_i $ to $v_i $ for $i <n+1$. Assign weight $0 $ to $v_i $ for $i >n$.

Connect $v_i$ to $v_{i+1}$ For $i =1,...,n-1$.

Connect $v_i$ to $v_{i+1}$ For $i =n+1,...,2n-1$.

Connect $v_i$ to $v_{i+n}$ For $i =1,...,n$.

Connect $v_i$ to $v_{i+n+1}$ For $i =1,...,n-1$.

Connect $v_{i+n}$ to $v_{i+1}$ For $i =1,...,n-1$.

If there is a solution to the partition problem then we can find two vertex disjoint paths in the graph corresponding to those partitions. On the other hand clearly if we can devide the graph into two connected sets of same size then we have a solution for partition.

Edit1: As Sasho mentioned in comments if the input graph is complete graph then thete is a straightforward reduction from partition problem. I leave previous reduction as it uses sparse graph.

Edit2: As asked in comments about other graphs except the complete graph I undeleted this answer, because even though it's easy, it's maybe non trivial.