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.
1
1
Replying to
how is it substantively different from plain min-cut? like on the path instead of god's-eye view or something?
1
Replying to
Exactly. It is to regular min cut as SLAM is to regular shortest path.
Replying to
Only looking for approximations. Can assume some common structure regime. Like a small world graph = cut the weak links. Scale free graph = disconnect hubs.
1

