Merging nodes of a DAG
I think instead of performing merge at the beginning. We can add a node which has the similar edges as the two merged vertices. 

Having the following DAG. 



If we want to merge node A and B. We add a new node which has the similar attributes as A + B. 



Then trasverse  from new node AB (should be Depth-first):


If it find Node A or B, then the merge should be cancelled because it creates a cycle. simply delete Node AB.
If we do not se Node A or B, the merge is valid so delete node A and node B.