# algorithm to delete nodes that completely removes connectivity [closed]

This is a distributed systems problem, but perhaps the graph theory gurus can help me.

I need an algorithm that that tells me which nodes to remove from the graph to completely remove connectivity.

See example:

The most intelligently thing to do would be to remove the bcasts nodes:

Can you help me? One way to solve this would using a SAT or ILP solver, but I want to if there are any other algorithms for this kind of task.

• What do you mean by "completely remove connectivity"? Why doesn't deleting BCast1 achieve that? Do you need to remove the minimum possible number of vertices? – David Richerby Feb 16 '17 at 17:28
• the nodes that are removed are cuts in the graph to disconnect the graph. removing BCast1 does not achieve that, because there is Bcast2 to enable communication between the nodes So i want to know if there a cut that breaks all supports? – Klaus Feb 17 '17 at 21:35
• Removing Bcast 1 disconnects the graph: there is no path from the right-hand client node to any other node. Are you in fact looking to disconnect some set of nodes? If so, you need to specify what set that is. – David Richerby Feb 18 '17 at 10:54
• Well yeah removing Bcast1 will disable communication at time T and I guess for graph theory that's a disconnect in the graph. But since we are modeling a live network, the client nodes will find a way to communicate in time T+1 via Bcast2, and there will be two client nodes connected to Bcast2. You could say that are different set of nodes and we need to find a way to prevent the client nodes from reaching the end of the graph. – Klaus Feb 18 '17 at 15:33
• You need to describe exactly what problem you're trying to solve. Your latest comment suggests that the graph is dynamic (edges may change over time) and that's the first time you mentioned this in the 24hrs since you posted your question! – David Richerby Feb 18 '17 at 15:46