I have a planar graph $G = (V, E)$ and I want to randomly generate partitions of $G$ into $k$ connected components. In the simple version, the size of the connected components needs to be as close to equal as possible (i.e., no more than $1$ apart). In the harder version, every vertex has a weight, and the sums of the weights needs to be as close to equal as possible.
How can I go about doing this? I feel like this problem has a flavor of NP-hardness, but I don't care about things like minimal edge cuts. Literally any division works.
The weighted version of the problem is NP-complete, even for $k=2$, because we can reduce subset sum to it. Suppose we have integers $x_1, \dots, x_n$, with $x_1 + \dots + x_n = S$, and want to find a subset with sum $T$. Give the complete bipartite graph $K_{n,2}$ (which is planar!) vertex weights as follows: the $n$ vertices on one side are assigned weights $x_1, \dots, x_n$, one vertex on the other side is assigned weight $S-2T$, and the other vertex weight $0$.
The total weight of all vertices is $2S-2T$. If a partition into two connected subgraphs, each with weight $S-T$ (as equal as possible) exists, then the component containing the vertex of weight $S-2T$ also contains a bunch of vertices whose total weight is $T$: the subset we were looking for.