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:

  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(𝑒, 𝑣)
  return the tree formed by blue edges

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

  Create a new tree rooted at π‘₯

UNION(𝒙, π’š)
  PARENT 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.

  • 2
    $\begingroup$ Given that your pseudo-code doesn't break the loop when the tree is finished, it's really irrelevant how many redundant edges you encounter early, because you'll traverse and query all of them. Concentrate on designing a graph for which most edges will do O(n) work when querying FIND. $\endgroup$
    – Mihai
    Mar 20 '16 at 9:05

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}))$


Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.