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

157 Views Asked by At

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

There are 1 best solutions below

4
On BEST 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$.