# re-rooting a rooted DAG

A "network" is a DAG with a single source (the "root") and all nodes except the root either have in-degree one or out-degree one. A network is "binary" if all nodes have degree (in-degree + out-degree) at most 3.

My Question(s): Are any algorithms known for re-rooting a given network N at a given node x?

That is, given a network N and a node x, I want to reverse edges such that the result is a network with root x. I'm not sure about whether or not I care to reverse as few edges as possible. I would like a strategy for the general case, but if anyone has an idea for the binary case, I'll be all ears as well...

Thoughts:

• since the old root r has a path to x in N and, in the new orientation N', x will have a path to r, at least one r-x-path needs to be completely reversed (Condition A) that's not true

• since N' is acyclic, there are no r-x-paths in N', so all r-x-paths in N need to have at least one of their edges reversed (Condition B) (see also the related question below)

• due to N and N' having the "network-property", every node z except r and x satisfies one of the following conditions:

• no incident edges of z are reversed
• all of z's incident edges are reversed
• one incoming and one outgoing edge of z is reversed
• all of z's incident edges are reversed, except one incoming and one outgoing edge
• some more observations:

• if there is exactly one r-x-path in N, then reversing this path gives the desired result
• if there are strictly more than one r-x-paths in N, then all of them must contain a node with in-degree strictly more than one (could be the same for all paths)

Related Questions: Here's one where someone wants to reverse a single edge in a DAG and restore the DAG property, which has been credibly argued to be reducible to Min Cut. However, in my question, there's the additional constraint of the "network-property"...