0
$\begingroup$

I'm working on a problem where I have a directed acyclic graph and I need to repeatedly flip all incoming (or outgoing, or both incoming and outgoing) edges from a single vertex. I think that resulting graph is still a DAG. Am I correct?

$\endgroup$
  • 1
    $\begingroup$ Consider the graph on the vertices $x,y,z,w$ with edges $x\to y$, $x \to z$, $y \to w$, $z \to w$. This is a DAG. If you reverse the orientation of all edges incident to $y$ then you get a directed square, which is not a DAG. $\endgroup$ – Yuval Filmus May 16 '17 at 18:01
  • $\begingroup$ @Yuval Filmus Yes, it seems you can only flip all incoming or all outgoing, not both of them at the same time $\endgroup$ – ghord May 16 '17 at 19:52
  • 2
    $\begingroup$ Have you tried proving that the graph remains a DAG? $\endgroup$ – Yuval Filmus May 16 '17 at 20:25
2
$\begingroup$

This doesn't hold if we flip both outgoing and incoming edges as shown by @Yuval Filmus.

Here is my try of a proof by contradiction for only flipping outgoing of incoming edges (sorry if it's too informal):

  1. After flipping all incoming(outgoing) edges from vertex v in a DAG G, we get another graph that is not a DAG (it has a cycle).
  2. Since we only changed the direction of the vertices incident to v, the only way we loose the acyclic property is if there is a new cycle going through vertex v.
  3. Since we flipped directions of all incoming(outgoing) edges from vertex v, all edges incident to vertex v are now outgoing(incoming), so it is not possible for any cycle to go through vertex v, which contradicts 2.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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