I want to find minimum vertices that connect certain vertices to each other. For example, assume list of edges is connections = [(2,0),(0,5),(2,3),(3,4),(0,4),(4,1),(5,1)] and the graph will be like below:
Then I want to know how to connect vertices 2, 4, 5 together with minimum number of vertices. Which in this case is vertex 0.
Therefore the output should be [0,2,4,5] which means 4 vertices needed. I tried to implement the algorithm with brute force since there would be more complicates cases but I am not sure how to find the best answer from all possible combinations.
from itertools import combinations
verticis = [0,1,2,3,4,5]
connections = [(2,0),(0,5),(2,3),(3,4),(0,4),(4,1),(5,1)]
key = [2,4,5]
i, j = 2, len(verticis)
res1 = [com for sub in range(j) for com in combinations(verticis, sub + 1)]
res2 = [com for sub in range(i - 1) for com in combinations(verticis, sub + 1)]
res = list(set(res1) - set(res2))