Label groups of vertices in a graph in an efficient manner without BFS/DFS

Question

I have a graph with a set of vertices $\mathcal{V}$ and a set of edges $\mathcal{E}$. There exists a path between every 2 vertices in the graph. To each edge there is an associated weight $w(e), e \in \mathcal{E}$. I define a (global) threshold $T$ such that if $w((u,v)) < T$ the two vertices $u,v \in \mathcal{V}$ are in the same group: $g \in \mathcal{V} \rightarrow \mathbb{Z}, g(v_1) = g(v_2)$. This behaviour is transitive. The goal is to label the distinct groups starting from zero (the order of the groups is irrelevant). I know that this can be achieved trivially with BFS or DFS, but I want to avoid using those.

The idea I came up with is to iterate over the vertices, go over their 1-ring neighbourhood, and create a new group every time that $w((u,v)) < T$ for any of the edges and neither $u$ nor $v$ have been assigned a group (for example $g(u) = g(v) = -1$). Additionally, each group is assigned a label, which is initially equal to the index of the group: $h:\mathbb{N} \rightarrow \mathbb{N}, h(g(u)) = g(u)$. If at some point $w((x,y)) < T$ and $w((y,z)) < T$, but $g(x) \ne g(z)$ then set $h(g(x)) \leftarrow \min(h(g(x)),h(g(z))$ and $h(g(z)) \leftarrow h(g(x))$. After this procedure it should hold: $h(g(u))=h(g(v)), u,v \in \mathcal{V}$ if there exists a path from $u$ to $v$: $\pi = e_1,...,e_n$ such that $w(e_i) < T$. Is the algorithm I came up with correct or did I miss something? As it is currently it requires $|\mathcal{V}|$ memory for each array $g,h$. Is there a way to optimize this further?

Answer 1

As you highlight in your comments, a reasonable approach is to delete all edges with weight $\ge T$, then compute the connected components of the resulting graph (using any standard algorithm for computing connected components).

Answer 2

I believe my algorithm is correct. A sketch of the proof is presented below:

There are 2 cases: either $u \ne v \in \mathcal{V}$ need to be from the same group, or they need to be from different groups (depending on whether there exists a path between them such that $w(e) < T, \forall e \in \pi$). It needs to be shown that the algorithm produces the resulting groups (the proof for each case will be done by contradiction).

1. Case 1: Let $u,v \in \mathcal{V}$ and there is a path from $u$ to $v$: $\pi=e_1,...,e_n$ such that $w(e_i) < T$. Then $h(g(u))$ should equal $h(g(v))$ for the algorithm to be correct.

2. Assumption of algorithm incorrectness: Assume that this is not the case, and that $u$, $v$ belong to different groups based on the result of the algorithm. For simplicity assume that $\pi = \pi_1,x,y,z,\pi_2;\, x,y,z\in \mathcal{V}$ such that all vertices from $\pi_1,x$ belong to $h(g(u))$ and all vertices on $y,z,\pi_2$ belong to $h(g(v))$ based on the algorithm. The case following the above assumption will be proven, but it should be clear that the same will hold by induction even if $\pi$ is split into more groups based on the algorithm.

Proof by contradiction: From (1), it follows $w(x,y)<T, w(y,z)<T$, and from (2) it follows: $h(g(x)) \ne h(g(z))$. From the definition of the algorithm it follows that it never splits groups, and it merges two groups if $w(x,y) < T, w(y,z)<T$ but $h(g(x)) \ne h(g(z))$. Since the algorithm goes over all edges it should have merged $h(g(x))$ and $h(g(z))$.

3. Case 2: $u,v \in \mathcal{V}$ and there is no path $\pi$ from $u$ to $v$ such that $w(e) < T, \forall e \in \pi$, then $h(g(u)) = h(g(v))$.

4. Assumption of algorithm incorrectness: Assume $h(g(u)) = h(g(v))$.

Proof by contradiction: Both at group creation and at group merging (the only two ways for vertices to end up in the same group) there needs to exist a path between $u$ and $v$ such that $w(e)<T, \forall e \in \pi$. (3) states that no such path exists, then $h(g(u)) \ne h(g(v))$.

Clearly the proof is fairly informal, so I may have missed something. I will leave the question open for a while, because 1) somebody may come up with a better & more optimized algoritm, and 2) I may have some mistake in my proof.