Given a DAG N, if an edge $(U \rightarrow V)$ is added between any existing nodes U and V. Then, by performing DFS from the node $U$ and checking whether there is a cycle or a not, should be sufficient to conclude that this addition of edge didn't violate the acyclic property of the given DAG. Is it correct?

Or there is a need to perform DFS from other nodes in the network to verify the cyclic property of DAG?

Trying to find the most efficient way to verify whether addition of an edge to an existing DAG introduces cycles or not?


1 Answer 1


If you start with a dag then the only thing you need to check is whether adding the edge $U\to V$ will not create a cycle. That is, there should not exist a path from $V$ to $U$ in the original graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.