Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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