1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ I have a few questions. Firstly by the constraint V1∩V2...∩Vn=∅, you want no vertex to be common for all clusters or did you want Vj∩Vi=∅ for i not equal to j? $\endgroup$
    – Vivek Bagaria
    Nov 27, 2013 at 15:50
  • $\begingroup$ He must mean no vertex belongs to every cluster, exactly as stated, since otherwise no connected graph has subgraphs satisfying the Cluster Condition. If the subgraphs partition the vertices, then some edge crosses the partition and thus belongs to no subgraph. Equivalently, if the subgraphs partition the edges, then some vertex must appear in more than one subgraph. $\endgroup$
    – Jeffε
    Nov 30, 2013 at 20:49
  • $\begingroup$ I messed up a part of the cluster condition and edited it. The union of E1, E2, ... , En doesn't need to be E. The important thing is that each vertex from V is used in exactly one cluster. $\endgroup$
    – CCguy
    Nov 30, 2013 at 23:25
  • $\begingroup$ METIS is worth looking at: glaros.dtc.umn.edu/gkhome/views/metis For Delaunay triangulations there should be something easier. Choose $n$ vertices of the graph at random and see if the vertices in each Voronoi region form a good clustering. Maybe that's a starting point. $\endgroup$
    – Andrew D. King
    Dec 6, 2013 at 1:34

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.