1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ It's not clear what you want the output to be. I'm not sure what precisely you mean by "propagate the effects of that". Can you provide a precise specification of what you want the updated graph to be, after reversing a single edge? Exactly which edges do you want changed, and how do you want them to be changed? You might need to use mathematics. What's the motivation for this? What's the context you encountered it in? $\endgroup$
    – D.W.
    Sep 14 at 16:15
  • $\begingroup$ Do you want to minimize the number of updated edges? $\endgroup$
    – Dmitry
    Sep 14 at 18:01
  • $\begingroup$ @Dmitry, yes. As an alternative, I might want to limit the maximum length of the update chain. $\endgroup$
    – Brannon
    Sep 14 at 18:25
  • $\begingroup$ @D.W. I've added some more context. $\endgroup$
    – Brannon
    Sep 14 at 18:25

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\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.