# Confluent directed acyclic graph

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.

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$.
• 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. May 16, 2018 at 9:28