GATE CS 2005 Q7 — Sets, Relations and Functions

A binary relation on a set of $n$ elements can be represented as a directed graph with $n$ vertices, where an edge exists from vertex $u$ to vertex $v$ if and only if $u$ is related to $v$.

Computing the transitive closure of this relation is equivalent to finding the all-pairs reachability in the corresponding directed graph.

• Warshall's Algorithm: The standard and most widely used algorithm to compute the transitive closure of a relation is Warshall's algorithm.
• Complexity: Warshall's algorithm uses dynamic programming with three nested loops, each running $n$ times:

  for k = 1 to n:
      for i = 1 to n:
          for j = 1 to n:
              reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

  This results in a time complexity of $\Theta(n^3)$, which is $O(n^3)$.

Therefore, the time complexity of computing the transitive closure is known to be $O(n^3)$.