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|$
- 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.
- 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.
- Draw this graph twice.
- In the first copy, remove every red edge beginning at even level, and every black edge beginning at odd level: $\mathcal{O}(E)$.
- In the second copy, remove every "black even" and "red odd": $\mathcal{O}(E)$.
- 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)$).
- For the second copy: The same for "$2i+1$".
- 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?