Conversation

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.
2
13
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
Replying to
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