Burning bridges problem: you're going from A to B on a graph, cutting some edges as you go. Is there an algorithm that will approximate max-flow/min-cut set of cuts while getting to B in reasonable time? Solve for cost function that's a weighted sum of shortest path and min cuts.
Conversation
You're allowed to wander, though of course not backtrack over edges you've already cut
Trying to pose clearly the problem of destroying a graph by disconnecting it as you pass through it ("burn the fields and salt the earth" sort of thing)
2
1
Replying to
Separate. You can choose to cut. Say it’s all bridges over canals like the Konigsberg problem and you have a finite set of bombs to use, fewer than bridges. Your goal is to efficiently disconnect 2 points while passing between them.
Replying to
how is it substantively different from plain min-cut? like on the path instead of god's-eye view or something?
1
Show replies

