1
$\begingroup$

A directed acyclic graph $G$ is confluent, if any two vertices ${v_1},{v_2}$ in $G$ which have a common ancestor $u$ also have a common successor $w$. (I.e. if there are paths from some $u$ to both ${v_1}$ and ${v_2}$, then there are also paths from ${v_1}$ and ${v_2}$ to some $w$. Vertices $u,{v_1},{v_2}$ and $w$ do not need to be distinct, thus e.g. a single "line" of vertices is trivially confluent) Design a linear-time algorithm that determines whether a given DAG $G$ is confluent.

Is the "line" with $3$ vertices $u \to v \to w$ s.t. ${v_1} = {v_2}$ trivially confluent? Or is it nesseccary to have ${v_1} \ne {v_2}$ and thus the smallest number of vertices such line may have is $4$ $u \to {v_1} \to {v_2} \to w$?

Edit: Solved the problem.

$\endgroup$
0
$\begingroup$

Yes, the "line" $u \to v \to w$ is trivially confluent, and so are the empty graph, the graph with a single node, and the "line" $u \to w$. In the case of a graph with a single node $v$ there is only one case to consider, with $v_1 = v_2 = v$. The common ancestor is then $v$ itself, and the common successor is also $v$.

$\endgroup$
  • $\begingroup$ Any examples of non-confluent DAG? $\endgroup$ – user_758 May 16 '18 at 9:09
  • 1
    $\begingroup$ Take any non-trivial tree oriented toward the leaves! For example $u \leftarrow v \rightarrow w$. Here $u$ and $w$ have $v$ as a common ancestor, and no common successor since they are leaves. $\endgroup$ – Rodolphe Lepigre May 16 '18 at 9:28

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.