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?
2026-04-29 08:30:45.1777451445
sufficient conditions to maintain acyclicity after flipping the direction of only one edge
157 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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$.