1
$\begingroup$

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

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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