Efficient algorithms for identifying the diamond fork&join vertices and the diamond pairs in directed acyclic graph?
$G=(V,E)$ is the graph we work on.

Problem 2: $\Diamond_F(reverse(G))=\Diamond_J(G)$, where $reverse(G)$ reverses all the edges of G.

Problem 3:
This can be solved in $O(nm)$ time. For each vertex $s$, find all the pairs $(s,v)\in \Diamond$ in $O(m)$ time. To do this and split every outgoing edge $(s,v)$ with a new vertex $v'$. Namely, delete edge $(s,v)$, and replace it with $(s,v')$ and $(v',v)$. Find the dominator tree with source $s$ in the new graph, which can be done in linear time for dags.

$(s,v)\in \Diamond$ iff $v$ is the children of $s$ in the dominator tree and $v\in V$.