I ran across a problem while working on an algorithm for a game I'm making on the side. It's basically a clustering problem where we have a graph G and want to split it into clusters of equal size where each cluster is a connected subgraph of G. I also wanted to minimize the number of clusters and keep some guarantees about their size. The graph will also change over time so I want some quick way to add and remove vertices and maintain the clustering properties I created for the original clusters.
I'm working on this myself at the moment but I don't want to waste time if there already exists some sort of solution for this problem or if I'm overlooking an easy solution. If y'all have any helpful algorithms or papers you could refer me to, that would be amazing. Also, if you straight up solve this, that would be great as well.
Here's a formalization of the problems:
Cluster Property: given undirected graph G = (V, E) with vertices V and edges E and a set of clusters $C=\{C_1, ..., C_n\}$ where each $C_k=(E_k, V_k)$, $C$ holds the following properties:
- $|C_k| \le a*ceil(\sqrt{|V|})$ where ceil is the ceiling function that rounds to up
- $n$ is minimized for graph $G$
- $C_k$ is connected
- $V_k \subseteq V$ and $E_k \subseteq E$
- the sets $V_1,\ldots,V_n$ are disjoint
- $V_1 \cup V_2 ...\cup V_n = V$
Problem 1
Input: an undirected graph $G = (V,E)$
Output: a set of clusters $C={C_1,...,C_n}$ where $C$ has the Cluster Property
Problem 2
Input: an undirected graph $G = (V, E)$, a set of clusters $C={C_1,...,C_n}$, and a set of valid edges and vertices to remove $R=(E_R,V_R)$
Output: a set of clusters $C'={C'_1,...C'_n}$ for graph $G_R=(V-V_R,E-(E_R\cup E_{V_R}))$ where $C'$ maintains the Cluster Property. $E_{V_R}$ is the set of all edges that have an endpoint in $V_R$.
Problem 3
Input: an undirected graph $G = (V, E)$, a set of clusters $C={C_1,...,C_n}$, and a set of valid edges and vertices to add $R=(E_A,V_A)$
Output: a set of clusters $C'={C'_1,...C'_n}$ for graph $G_A=(V \cup V_R,E \cup E_A)$ where $C'$ maintains the Cluster Property.
Note: when adding or removing edges to the graph, assume that valid edges have endpoints in vertices that exist in the final graph.
Edit: There are a couple extra constraints I have that on the graph that I haven't provided. I'd like to be able to solve this problem for undirected graphs in general but if that's not possible or it's too difficult, I'll be forced to solve it for the specific set of graphs I'm working on. These graphs are Constrained Delaunay Triangulations, I can go into this more if you'd like.
