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

Question

(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).

Answer 1

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.

You can check our paper, Efficient enumeration of solutions produced by closure operations, to look at the details https://arxiv.org/abs/1712.03714