8
$\begingroup$

Given a connected graph $G$ and a subset of its vertices, $S$, I need to find the smallest connected subgraph of $G$ containing all of $S$. How would you approach this in Mathematica?


I am asking this here on Mathematica.SE because I am looking for the most convenient way to use the functions Mathematica already provides to tackle the problem.

$\endgroup$
  • $\begingroup$ How do you measure size? As a sum of edge weights? $\endgroup$ – kirma Oct 28 '15 at 17:02
  • $\begingroup$ @kirma Just the number of edges is good. The solution is going to be a tree. $\endgroup$ – Szabolcs Oct 28 '15 at 21:13
2
$\begingroup$

This is a well-known NP-hard problem known as Steiner tree. The problem is computationally difficult from many viewpoints. So, it is good to remember that it is highly unlikely to get a fast algorithm to handle every case.

Let me present a brute-force method with one small heuristic. The algorithm is an exact one, i.e., it is guaranteed to find the optimal solution for any graph. Let us check the pairwise distances of each pair of terminals in $S$, and let $d$ be the maximum distance between any two terminals. It is easy to see that the tree we choose (not including the vertices from $S$, that is) has to be of size at least $d-1$, for otherwise there is at least one pair of terminals that cannot be connected. Using this observation, we proceed as follows:

g = RandomGraph[{12, 18}, VertexLabels -> "Name"];
s = RandomSample[VertexList[g], 3]; (* Choose some S. *)
HighlightGraph[g, s]

(* Compute a lower bound on the solution. *)
lbound = Max[GraphDistance[g, First[#], Last[#]] & /@ Subsets[s, {2}]] - 1;

(* Generate candidate vertex subsets, and take the first suitable one. *)
trees = Subsets[Complement[VertexList[g], s], {lbound, Infinity}];
t = SelectFirst[Subgraph[g, #] & /@ (Union[#, s] & /@ trees), ConnectedGraphQ];

HighlightGraph[g, t]

Note: make sure the set $S$ does not contain isolated vertices; in fact, we might well get rid of such vertices before running the algorithm.

A nicer still quite easily implementable approach is the dynamic programming algorithm of Dreyfus and Wagner, but I'm not sure how nicely Mathematica lends itself to it. On my hardware, the above code handles instances with +20 vertices still in a few seconds; much depends on the structure of the graph, and on the size of $S$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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