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
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
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