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
Replying to
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
Obviously, one extreme is to just traverse the whole graph (eulerian circuit) and solve the min-cut explicitly and then do the shortest path that allows you to cut them as you go from A to B in the final pass.
1
1
Another extreme is to solve shortest path, cut everything not on it, then cut shortest path as you finish. Both seem very inefficient.
2
1
More general version you have several pairs of points and must disconnect all pairs while traveling between one pair.
Or… there are n coordinating travelers doing the burning, with or without constant communication.
1
1
The last one is a graph theory formulation of the maneuver warfare problem: collapse a force structure from within, preferably in radio silence… for more spatial realism assume the graph is a spatial maze (ie it’s on a plane and you have gps+ compass)
1
2
Forgot to explicitly state a crucial condition: you don’t know the graph upfront but must discover it by traversing it. Like SLAM (simultaneous localization and mapping) vs shortest path or D* vs A*.
1
2
The STAB problem: simultaneous traversal and burning.
For a positive use case… traversing a forest and doing control burns as you go to disconnect it for wildfire resistance.
5

