having a bidirectional graph, best way to remove paths that join certain nodes?

Question

Imagine i have a bidirectional graph with 4 nodes with the following connections:

0 <-> 2 ; 0 <-> 3 ; 1 <-> 2 ; 1 <-> 3

now imagine i have a group of nodes K (0 and 1), and i want to calculate the minimum amount of connections i have to remove so that those nodes aren't ALL connected.

0 <-> 3 ; 1 <-> 2

this way theres no path that can connect 0 and 1. in fact even if the group of nodes K were something like 10 nodes, 9 could be connected if at least 1 isn't (thats why i used high case for "all" above).

another example would be:

0 <-> 2 ; 0 <-> 3 ; 0 <-> 4 ; 1 <-> 2 ; 1<->3

and a group of nodes K (0, 1, 4) i would only need to remove 1 connection to avoid them ALL connecting

0 <-> 4

I've tried a lot of things on my own, like calculating all paths of the K group and checking for repetitive paths and removing those, but it doesn't work for all cases (like the first one i posted above).

is there an algorithm that can help me with this? i've tried google but i cant find documentation for this type of problem, maybe its not very common.

thanks in advance.

Answer 1

Example 1: From your graph:

(0,2),(0,3),(1,2),(1,3)

      2
    /   \
   0     1
    \   /
      3

K(0, 1)

Create a tree like this:

     0
    / \
   2   3
  /     \
 1       1

Each branch begins at 0 and ends at 1. If a branch does not reach 1, it's not included. Remove the topmost edges (in case of branching below that point). It doesn't matter if you build the tree from 0 to 1 or from 1 to 0 since the graph is bidirectional.

Example 2: Graph:

  (0,1),(1,2),(2,3)

  0 -- 1 -- 2 -- 3

K(1, 2)

Tree:

1
|
2

Remove:

  (1,2)

Example 3: Graph:

(0,2),(0,3),(0,4),(1,2),(1,3)

    0
  / | \
 2  3  4
 \ /
  1

K(0, 1, 4)

Tree:

   0
 / | \   <-- 2 edges leading to 1; 1 edge leading to 4
2  3  4
|  |
1  1

Remove:

(0,4)

Answer 2

You can count the number of edges that each node has. If you disconnect all the edges from a node, you disconnect the graph. So, the minimum amount of connections you have to remove is the number of edges that the vertex with the least edges has.

Say your graph has bidirectional connections 0-1, 0-2, 0-3, 2-3, 3-1. 0 has 3 edges connecting it. 3 has 3 edges connecting it. 1 has 2 edges connecting it. 2 has 2 edges connecting it.

So you should remove 0-2 and 2-3 to disconnect 2 from the graph. Now you can no longer go from 2 to any of the other points.