Compute relational composition in $O(|E||V|)$

Question

Definitions: Let $G=(V,E)$ be a DAG without self-loops, and $X \subseteq G$ and $Y \subseteq G$ be graphs.

Input: $X,Y$. Output: The relational composition relational composition $X \circ Y$ in $\mathcal{O}(|E||V|)$.

• Case 1: $|E| \le |V|$. Two for loops over $E(X)$ and $E(Y)$: Runtime $ \le \mathcal{O}(|E|^2) \le \mathcal{O}(|E||V|)$.
• Case 2: $|V| \le |E|$
  1. Draw the graph $(V(G),E(X) \cup E(Y))$: $(O(|V|)+\mathcal{O}(|2E|)))$. We call edges from $E(X)$ black and from $E(Y)$ red.
  2. Topologically sort it (Kahn: $\mathcal{O}(|V|) + \mathcal{O}(|E|)$). Let the first level be $0$, and edges go from a level to a higher level.
  3. Draw this graph twice.
  4. In the first copy, remove every red edge beginning at even level, and every black edge beginning at odd level: $\mathcal{O}(E)$.
  5. In the second copy, remove every "black even" and "red odd": $\mathcal{O}(E)$.
  6. For the first copy:
     • for all nodes $u$ on level $2i$
     • for all nodes $v$ on level $2i+1$
     • report edge $(u,v)$ (Runtime $\mathcal{O}(V^2) \le \mathcal{O}(EV)$).
  7. For the second copy: The same for "$2i+1$".
  8. Union the reported nodes, throw out duplicates $\mathcal{O}(V^2) <= \mathcal{O}(EV)$ (I hope the graph representation allows this).

Could some of you please look over my algorithm and check whether

• it is correct
• it is in $\mathcal{O}(|E||V|)$

If it's correct, does my algorithm already "exist"? If not, could you provide an alternative? I'll accept the first answer, but upvote if some more people are so kind to check.

EDIT: Step 6 Seems to be in $O(E^2)$ sometimes. I wish this would not be true. Has anyone a working algorithm?

Answer 1

The problem is in Step 6 (from my understanding).

Essentially, you idea is to check for sequences $(u,w)(w,v)$ whether $(u,w) \in E(X)$ and $(w,v) \in E(Y)$. The topological sorting is correct, since in such sequences the two edges must come after each other.

An edge $(u,w)$ is black if it belongs to $E(X)$. An edge $(w,v)$ is red if it belongs to $E(Y)$. An edge may have two colors in this case.

A node $u$ will check each neighbor $w$ [s.t. $(u,w)$ is black] if $w$ has a red edge $(w,v)$ for one of its neighbors. In this case: $\sum _{u \in V} deg(u). \sum _{w \in N(x)} deg(w) = O(E^2)$

From what I understood: you made some filtering of some unneeded edges (step 4,5)- however there may be a worst case that will lead to complexity higher than $O(E^2)$.

Answer 2

Theorem 2.29 on page 60 of Parsing Theory of Sippu and Soisalon-Soininen gives an algorithm for computing (among other operations on relations) the composition of two relations. The algorithm runs in $O(t(|V|+|E|))$ time, where $t$ is the time needed to perform union or assignment operations on sets of vertices. The result of this operation is a set of vertices per vertex representing its neighbors. This algorithm works on arbitrary graphs, not just acyclic ones.