# Efficient algorithm/ implementation to compute Transitive Closure of a Rule with respect to a Relationship

(Recalling some) Definitions:

1. Fix a finite collection of finite sets: $$A_1,\ldots,A_k$$. Then relationship $$R\subseteq A_1 \times A_2 \times \ldots\times A_k$$. (Remark: $$A_i$$'s need not be distinct.)
2. A rule (or transition) $$\sigma: R^m \to A_1 \times A_2 \times \ldots\times A_k$$.

Examples:

1. Consider the ancestor relationship $$R = \{(x,y)\mid x \text{ is an ancestor of } y\}$$. Then the rule $$\sigma: R^2 \to A \times A$$ is given by $$\sigma((x,y),(y,z)) = (x,z)$$ represents the transitive rule that if $$x \text{ is an ancestor of } y$$ and $$y \text{ is an ancestor of } z$$ then $$x \text{ is an ancestor of } z$$.

2. Consider the 3-cycles relationship $$R = \{ (x, y, z) \mid x\rightarrow y \rightarrow z \rightarrow x \text{ is a directed cycle of a Graph}\}$$. Then the rule $$\sigma: R \to R$$ given by $$\sigma((x,y,z)) = (y, z, x)$$ represents the cyclic order symmetry relation.

Question-1: Given $$\sigma$$ and $$R$$, what is an efficient algorithm to compute the transitive closure of $$\sigma$$ with respect to $$R$$?

(Remark: Some naive/ obvious approaches I thought of so far:

1. (Brute force: ) Loop through all $$e\in R^m$$,check if $$e$$ satisfies conditions of $$\sigma$$, if yes then add $$\sigma(e)$$ to $$R$$. Repeat until no more new elements can be added. $$O(|R|^m)$$.

2. For example-1 with a binary relationship and transitive rule, I know about Floyd-Marshall Algorithm. $$O(|A|^3)$$. There are 3 independent variables $$x, y, z\in A$$. Looping through them would be $$O(|A|^3)$$. But surely Floyd-Marshall is more superior than brute force looping over $$x, y, z\in A$$.

3. Using the independent variable trick one gets $$O(|A|^p)$$, where $$p$$ is number of independent variables. At this stage we need to check if all conditions satisfy or not. So in the most general case this is a $$\mathrm{SAT}$$ problem and hence probably no hopes of doing better. However I would love to know more about if anything more is known than what I am thinking about naively.)

Question-2: Is there a software package that already implements this? (I prefer Python, but any language should be fine).

• What is your definition of the transitive closure of $\sigma$ with respect to $R$?
– D.W.
Commented May 9, 2023 at 8:07

I give here an answer for a very specific subcase. We let $$x \in A_1 \times \dots \times A_k$$ be written $$(x^1,\dots,x^k)$$.
When the rule $$\sigma$$ acts on each $$A_i$$ independently, in the same way, that is $$\sigma(x_1,\dots,x_p) = (\sigma(x_1^1,\dots,x_p^1),\dots, \sigma(x_1^k,\dots,x_p^k))$$ there are better algorithms. In particular, when the $$A_i$$ are of size $$2$$, that is you compute the closure of sets by set operations, the complexity of computing the closure is well understood. You get a complexity linear in the size of the closure you are computing times a polynomial in $$k$$. The only exception, is for the closure by union, for which the complexity is slightly worse: linear in the size of the closure times |R|.
To get the best possible complexity, there are different methods depending on the rules. But there is a general method with a decent complexity using backtrack search: You consider a partial solution $$(x_1,\dots,x_i)$$ for $$i \leq k$$ and it is possible to decide whether it can be extended into an element of the closure, which allows to efficiently produce all solutions by a search tree, pruning the branch without solution. This method does not always work efficiently when $$|A_i|>2$$ or when the rule does not act coordinate-wise.