Flip directions in a graph so each node is a tail at most once I have a list of dependent pairs: A → B (B depends on A), B → C, D → C, etc. These would form a directed graph. I am allowed to flip the dependency of each pair. What I want to end up with is that no node should depend on more than one other node. A node having multiple dependents is fine. Cycles are fine. What is a good algorithm to do this? Ideally it would be fast and seek to preserve the original dependencies (minimize flips). Sorry if I do not have the adequate terminology to phrase the question better. Thank you.
 A: I will WLOG change the definition from "each node is a destination at most once" to "each node is a source at most one". I find it easier to reason about.
Let $G$ be the underlying undirected graph.
If we have a correct orientation, each node have at most one outcoming arc, so we can follow the path formed by these outcoming arcs in a unique way. There is two possible behaviors: We end on a node without any outcoming arc, or we end on a cycle. A connected component of $G$ can't have two cycles (check if two cycles are not disjoint, or if two cycles are disjoint, but linked by a path). However, if we have only one cycle, it is easy to find an orientation (orient the cycle in some way, and the other edges toward the cycle). We get that $G$ must be a pseudoforest.
Lets try to minimize the flips:
Suppose at first that $G$ is a tree. We must choose a root, that will be the only node without an outcoming edge. The number of flips is the number of edges not directed toward the root. The number of flips can be computed in linear time by a simple DFS. We can compute this for every node of the tree in $\mathcal{O}(n^2)$ so polynomial, but we can do better:

*

*Choose one node as root and compute for each node the number of flips for each subtree. This can be computed by a simple DFS from the root (not considering orientation). The number of flips of a node $u$ is the number of flips of the children of $u$ in the DFS + the number of flips on arcs linking to children of $u$.

*Do another DFS (without considering orientation). Each time you encounter a node, you will consider it at the root. You only need to update the number of flips on the node you came and the node you arrived. Lets supposed you moved from $u$ to $v$. Number of flips on $u$ become the sum of flips on the neighbors of $u$ (except $v$) + the flips on adjacent edges.
Number of flips on $v$ become the sum of flips on the neighbors of $v$ + the flips on adjacent edges. This can all be done in linear time.

Suppose now that $G$ is a $1$-tree (a graph with only one cycle). You don't have the choice for orientation of arcs not on the cycle, they need to be oriented toward the cycle. Choose a direction for the cycle with a minimal number of flips.
Do that for every tree and $1$-tree of the pseudoforest, and you are done.
