reverse single edge in DAG and keep it a DAG

Question

If I reverse a single edge in a DAG, how can I efficiently propagate the effects of that (e.g. change other edges) such that I don't introduce any cycles by said reversal? Is there a named algorithm for this that I should look up? I see some other questions about reversing an entire DAG; I'm only concerned with a single edge plus its necessary influence, which I hope is not the entire graph in a typical case.

To add more context: I'm working with some disjunctive job-shop representations. Example: https://acrogenesis.com/or-tools/documentation/user_manual/manual/ls/jobshop_def_data.html . I want to minimize the number of updated edges. And after the update, I still need all of the nodes in the graph to be accessible through some path.

Answer 1

I would suggest the following:

If you know a topological sorting $(s_0, …, s_{n-1})$ of your DAG and you want to reverse the edge $(s_i, s_j)$, $i < j$:

Input: DAG G = (S, A), topological sorting (s0, s1, …, s{n-1}), indices i < j

for each k from i to j - 1 do
    if (s_k, s_j) ∈ A then reverse (s_k, s_j)

Given the definition of the topological sorting, the resulting graph would be a DAG. Indeed, the order $(s_0, …, s_{i-1}, s_j, s_i, s_{i+1}, …, s_{j-1}, s_{j+1}, …, s_{n-1})$ would be a topological sorting.

Answer 2

I believe this can be formulated as a min-cut problem, and thus solved with an algorithm for max-flow.

Suppose you want to reverse the edge $s \to t$, and turn it into the edge $t \to s$. That will pose a problem for every other path $s \leadsto t$, because each such path will create a cycle in the graph. So, we can reformulate the problem as follows. Delete the edge $s \to t$. Now, find a minimum set of edges to remove, so that if we remove them, there are no remaining paths $s \leadsto t$.

This is exactly a min-cut problem. In particular, this is the problem of finding a $(s,t)$-minimum cut in the graph (after deleting the edge $s \to t$, and treating each remaining edge as having capacity 1). Thanks to the max-flow min-cut theorem, you can solve such a min-cut problem with any algorithm for max flow.