1
$\begingroup$

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

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.