# sufficient conditions to maintain acyclicity after flipping the direction of only one edge

Given a DAG $G=(V,E)$, Let $\dot{G}$ be $G$ after flipping the direction of a single edge $e\in E$. Are there sufficient (and\or necessary) conditions under which $\dot{G}$ is guaranteed to be DAG ? Are there known classes of DAGs that maintain this property?

-

## 1 Answer

Well, if $e=(v,w)$ is an arc in $E$, then an obvious necessary and sufficient condition for $\dot{G}$ to still be a DAG is that $(v,w)$ is actually the unique directed path from $v$ to $w$ in $G$.

For a specific graph, this condition can be checked using, for example, the Bellman-Ford algorithm on $G\setminus e$.

-
thanks though this is a very strong requirement. Are there other more relaxed requirements? For instance, Let $G$ be k-partite directed graph where all edges point left to right. Then flipping one edge will still maintain acyclicity as there is no back edge to form a directed cycle. –  seteropere May 11 at 19:14
I guess you mean $k=2$. But that example is a very strong structural requirement, both on the graph and the orientation. I'm not sure if there's a less simple-minded condition than mine for general digraphs, but if you have additional structure on $G$, then maybe you can say something better. –  Casteels May 11 at 20:21
I believe it holds for any $k>2$ as long as all directions go from left to right (or the opposite).. flip any edge and you wont go back to it; is my intuition make sense? –  seteropere May 12 at 20:30
What do you mean by "left" and "right" when $k>2$? In any case, consider a triangle (which is a $3$-partite graph). There has really only one acyclic orientation, and it has an edge whose reversal does not produce a DAG. –  Casteels May 12 at 20:49