How to find minimum vertices that connect certain vertices to each other

Question

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

Answer 1

This problem is in fact a well-known NP-hard combinatorial optimization problem: Steiner tree problem.

Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices) and minimizes the total weight of its edges.

In other words:

A minimum Steiner spanning tree (or simply Steiner tree) of S is a tree of minimum total length whose nodes are a superset of the given set S. Those nodes that are not points of S are generally called Steiner points (source).

Because of the intrinsic hardness of the problem, exact approaches for obtaining a minimum Steiner tree are all of exponential worst-case time complexity (unless P=NP). You can find various exact solution approaches to the problem in the literature. However, one simple exact approach is to model the problem instance in hand to a constraint optimization problem (COP), and solve it using a COP solving tool like MiniZinc:

include "steiner.mzn";
var int : weight;
array[1..6] of var bool: vertex;
array[1..7] of var bool: edge;

constraint vertex[3] = true;        % v2 is a terminal
constraint vertex[5] = true;        % v4 is a terminal
constraint vertex[6] = true;        % v5 is a terminal
constraint steiner(6,7,[1,1,1,2,2,4,4],[3,5,6,5,6,3,5],[1,1,1,1,1,1,1],vertex,edge,weight);

solve minimize weight;

In this code, the boolean decision variable vertex[i] indicates that whether or not the Steiner tree contains the (i-1)th vertex . In the instance you described we have three terminals. Therefore, we need to set the value of the corresponding decision variables as true. The objective of connecting these three nodes using minimum number of vertices is equivalent to finding a minimum Steiner tree, provided that the edge weights are all one. Hence, in the global constraint steiner, we set all the edge weights to one. An optimal solution to the given instance is as follows:

----------
weight = 3;
vertex = array1d(1..6, [true, false, true, false, true, true]);
edge = array1d(1..7, [true, true, true, false, false, false, false]);
----------

As can be seen, only the vertex 0 need to be employed as a Steiner point (vertex[1] is true in the returned solution), and the corresponding Steiner tree has three edges (i.e., {0,2}, {0,4}, and {0,5}). For more information on the global constraint steiner, see this link.