# 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. – Rodolphe Lepigre May 16 '18 at 9:28
{"ft_lang_label":"__label__en","ft_lang_prob":0.94708973,"math_prob":0.99980396,"size":750,"snap":"2019-51-2020-05","text_gpt3_token_len":255,"char_repetition_ratio":0.14745308,"word_repetition_ratio":0.0,"special_character_ratio":0.352,"punctuation_ratio":0.11949685,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999169,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-01-23T21:18:30Z\",\"WARC-Record-ID\":\"<urn:uuid:2f9c8e7a-436c-41d4-9875-bada0d466bc5>\",\"Content-Length\":\"132612\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:fa69b874-6177-424a-9147-f552564827f2>\",\"WARC-Concurrent-To\":\"<urn:uuid:98f2c22f-e6c4-46f8-9c23-10f8b2d48153>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/91972/confluent-directed-acyclic-graph\",\"WARC-Payload-Digest\":\"sha1:DN4CJZQUU4EQDYAOJTJONL7NA6UKYFGA\",\"WARC-Block-Digest\":\"sha1:4OBX4CHYGY5KFN44ZNFMGHLWZ6NEI77G\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-05/CC-MAIN-2020-05_segments_1579250613416.54_warc_CC-MAIN-20200123191130-20200123220130-00489.warc.gz\"}"}