Find a graph for which Kruskal's algorithm achieves worst-case running time

Question

I am working on a problem in which I must find a graph with edge weights on n vertices, for which Kruskal's algorithm achieves worst-case running time. I am using a UNION-FIND data structure, but with no optimisations (path compression or weight/height union rules).

The version of Kruskal's which I am using is as follows:

Kruskal(G)
  for each vertex 𝑣 ∈ 𝑉 do MAKE−SET(𝑣)
  sort all edges in non-decreasing order
  for edge 𝑢, 𝑣 ∈ 𝐸 (in the non-decreasing order) do
    if FIND 𝑢 ≠ FIND(𝑣) then 
      colour (𝑢, 𝑣) blue
      UNION(𝑢, 𝑣)
  od
  return the tree formed by blue edges

Also, MAKE-SET(x), UNION(x, y) and FIND(x) are defined as follows:

MAKE-SET(𝒙)
  Create a new tree rooted at 𝑥
  PARENT(𝑥)=x

UNION(𝒙, 𝒚)
  PARENT FIND(𝑥) ≔ 𝐹𝐼𝑁𝐷(𝑦)

FIND(𝒙)
  𝑦 ≔ 𝑥
  while 𝑦 ≠ PARENT(𝑦) do
    𝑦 ≔ PARENT(𝑦)
  return y

After having looked at this post, my idea was to construct a graph on n vertices, such that there are as many redundant edges as possible and at least one necessary edge which is checked last (this edge must have the greatest weight).

I've looked at the specific cases n = 4 and n = 5 and have tried to construct such graphs in these cases. However, I am struggling to generalise to arbitrary n.

I would appreciate any hints for progressing with this problem. Thank you.

Answer 1

Let the answer be a complete graph $G = (V,E)$ with $|V| = n$ and a weight function $W : E \to \mathbb{R}$

Let the vertices be denoted by $1,2,\dots n$ and edges between $i$ and $j$ as $(i,j)$.

Now define the weights of all the edges as follows: $$W(i,j) = j-1, \forall \ 1 \le i < j$$

(Assuming you break ties for the edges on the basis of the value of the nodes $i,j$)

If you add a break statement once all $n$ nodes have been merged, then the algorithm will iterate on all the $\binom{n}{2}$ edges (except the last $n-1$) before finishing execution. This is because it will iterate all the edges in non decreasing order and it will find that except for the edge $(1,j)$ all other edges connect nodes belonging to the same disjoint set.

The running time will thus be $\mathcal{O}(\alpha(n + \binom{n}{2}))$