7
$\begingroup$

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?

$\endgroup$
0
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thanks, you are right! I can not report all node pairs, I must follow the edges. Hmm yes I think this can lead to $O(E^2)$. I think my algorithm can not do it :( $\endgroup$ – Johannes Oct 13 '12 at 21:56
  • $\begingroup$ so does that answer your question ? $\endgroup$ – AJed Oct 14 '12 at 17:01
  • $\begingroup$ Well, more or less. Wish someone would find an alternative for step 6, but you'll get an accept. $\endgroup$ – Johannes Oct 14 '12 at 20:49
6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Looks nice, though I do not have access to this book, not even from university :( $\endgroup$ – Johannes Oct 13 '12 at 15:14
  • $\begingroup$ @Johannes, try your university's library - I don't have access to the book either, and I got it from my university's library as well. $\endgroup$ – Alex ten Brink Oct 14 '12 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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