title: Finding a minimum/maximum weight Steiner tree
body: <p>I asked this question on reddit, but haven't converged on a solution yet.  Since many of my searches bring me to Stack Overflow, I decided I would give this a try.  Here is a simple formulation of my problem:</p>
  
  <p>Given a weighted undirected graph G(V,E,w) and a subset of vertices S in G, find the min/max weight tree that spans S.  Adding vertices is not allowed.  An extension of the basic model is adding edges with 0 weight, and vertices that must be excluded.  This seems similar to the question asked here:</p>
  
  <p><a href="https://stackoverflow.com/questions/13146710/algorithm-to-find-minimum-spanning-tree-of-chosen-vertices">Algorithm to find minimum spanning tree of chosen vertices</a></p>
  
  <p>There is also more insight into what values the edges can take.  Each edge is actually a correlation probability, which I can encode in several ways, so the main questions I want to ask the graph are:</p>
  
  <ol>
  <li>Given k vertices that must be connected, what are the top X min/max spanning trees that connect them, and what vertices do they pass through?  As I understand it, this is the same question as asking the graph what is the highest probability of connecting all of the k vertices.</li>
  <li>Getting more vague, is there a logical way to cluster the nodes?</li>
  </ol>
  
  <p>As for implementation, I have the boost libraries installed, and once I get the framework rolling on this problem, I can deal with how to multi-thread it (if appropriate), what kind of graph to use, and how to store/cache the data, since the number of vertices and edges is going to be quite large.</p>
  
  <p><strong>Update</strong>
  Looking at the problem I am trying to solve, it makes sense that it would be NP-complete.  The real world problem that I am trying to solve involves medical diagnoses; specifically when the medical community is working on a problem with a specific idea in mind, and they need to take a step back and reconsider how they got there.  What I want from the program I am trying to design is:</p>
  
  <ul>
  <li>Given several conditions, tests, symptoms, age, gender, season, confirmed diagnosis, timeline, how can you relate them?  What cells/tissues/organs/systems are touched?  Are they even related?</li>
  <li>Along with the defined groups that conditions/symptoms can belong to, is there a way to logically group the conditions/symptoms?</li>
  </ul>
  
  <p><strong>Example</strong>
  Flu-like symptoms, red eyes, early pneumonia, and some of the signs of diabetes.  Is there a way to relate all of the symptoms?  Are there some tests that could be done to make it easier to determine?  What systems are involved?</p>
  
  <p>It just seemed natural to try and map this to a graph, or several graphs, and use probabilities as the correlation between different symptoms/conditions.</p>