Find a weight threshold for edges for maximum number of connected components in a graph

Question

So the problem starts with a graph in which every node is connected with every node by a weighted edge. The goal is to find a weight treshold W, so that every edge that has a weight lower than or equal to W gets removed, which results in the maximum amount of connected components. A connected component is defined as at least two connected nodes.

I've thought about sorting all the weights of the edges from high to low, then iterating through that list and setting the treshold equal to the current weight and check if the current amount of components is the highest amount we've had thus far.

Would this be an efficient algorithm? Also, the graph is undirected.

Added: If two tresholds W1 and W2 produce the same maximum amount of components, then the treshold for which the least amount of nodes are in a connected component is chosen. In other words, the treshold for which there are the most amount of free nodes.

Clarifications: The application is a graph for plagiarism detection. Each pair of nodes has a weighted edge connecting them, where the weight represents the probability of plagiarism between the two. A "free node" is defined as a node that is not connected with any other node.

Let's say the treshold is a weight of 80. When a node (which represents some submission) doesn't have an edge with weight higher than 80 to any other node, it's a free node.

Answer 1

Let $W = \{w_1, \dotsc, w_m \}$ be the set of weights (assume that all weights are different for simplicity). Without loss of generality assume that $w_1 > w_2 > \dotsc > w_m$, and the graph is connected. Note that the sorted order can be obtained in $O(m \log m)$ time.

An efficient algorithm can make use of union-find data structure as follows:

1. Start with threshold of $w_1$. In this case, the graph has only a set of free nodes. Thus, the number of connected components are 0 (as per the definition of a connected component given in the question). Let $num$ denote the number of connected components. Initially $num = 0$.
2. Repeat the following for every $w_i$ in order $(w_2 \to w_3 \to \dotsc w_n)$: add $w_i$ weighted edge to the existing graph. Let $w_i$ is incident on vertices $u$ and $v$. There are four possible cases:

• If $u$ and $v$ belongs to different connected components, update $num \leftarrow num -1$.
• If both $u$ or $v$ are free nodes, update $num \leftarrow num + 1$.
• If $u$ and $v$ belongs to the same connected components, $num$ stays the same.
• If exactly one of $u$ or $v$ is a free node, then $num$ stays the same.

This procedure gives number of connected components for every threshold $w_i$. Choose the one that gives the maximum number of connected components.

Using the union-find data structure, the above procedure can be implemented in $O(|V| \log |V| + m)$ time (as per aggregate analysis). Thus, the overall running time is $O((|V| + |E|) \log |V| ))$, where $|E| = m$ denote the number of edges and $|V|$ denote the number of vertices.