2
$\begingroup$

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:

enter image description here

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – David Richerby Feb 16 '17 at 17:28
  • $\begingroup$ 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? $\endgroup$ – Klaus Feb 17 '17 at 21:35
  • $\begingroup$ 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. $\endgroup$ – David Richerby Feb 18 '17 at 10:54
  • $\begingroup$ 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. $\endgroup$ – Klaus Feb 18 '17 at 15:33
  • $\begingroup$ 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! $\endgroup$ – David Richerby Feb 18 '17 at 15:46
2
$\begingroup$

Your problem is: given a graph, find a minimum-sized set of vertices whose removal disconnects the graph.

This is the "minimum vertex cut" problem. There are standard algorithms for this, based on network flow and the max-flow-min-cut theorem. You need to modify the graph slightly to make two copies of nodes, then apply network flow (network flow on the original graph finds a minimum edge cut; you want a minimum vertex cut). See https://en.wikipedia.org/wiki/Vertex_separator, https://en.wikipedia.org/wiki/Cut_(graph_theory), https://cstheory.stackexchange.com/q/2877/5038.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That doesn't seem to be what the problem is, since the asker is insisting that deleting the node BCast1 doesn't "disconnect" the graph. $\endgroup$ – David Richerby Feb 18 '17 at 10:54
  • $\begingroup$ And, now, we find out that the graph is dynamic! $\endgroup$ – David Richerby Feb 18 '17 at 15:46

Not the answer you're looking for? Browse other questions tagged or ask your own question.