On math.se, Sybren Zwetsloot has asked for help with an unusual optimal subtree problem. Here's my understanding of what he's asking:
We have a weighted bipartite graph on two sets $N$ and $B$, call them "nodes" and "buses", with $|N| \geq |B| + 1$. Furthermore (I believe), every bus $b \in B$ has degree $\geq 2$. We want to choose a maximum-weight subtree (or possibly subforest; Zwetsloot seems to be asking both questions) in which every element of $B$ has degree exactly $2$. Omitting some nodes is fine, but the resulting graph must be acyclic.
(Zwetsloot's original question uses the word "elements" instead of "nodes," but this name can be confused with elements of a set, so I changed it here.)
I proved the following partial result:
The maximum-weight subtree includes, for each bus $b \in B$, the connection with maximum weight among all connections of $b$. If multiple connections are tied for maximum weight, then each of them can appear in a different optimal tree. This is also true of the maximum-weight subforest.
This result lets us divide the graph into $|N|$ "complexes", each containing one node $n$ plus all the buses $b$ such that the edge from $n$ to $b$ is the highest-weight edge connection to $b$. We now have to make an acyclic graph on these complexes by connecting buses in one complex to nodes in another. The degree constraint on buses, though, precludes the usual MST algorithms that make greedy choices of additional edges: there are simple counterexamples (my answer on math.se provides one) for which adding the highest-weight available connection between two complexes forces suboptimal choices later on. Another possibility might be adapting bipartite matching algorithms for choosing remaining node–bus connections, but the no-cycles constraint also makes this difficult.
In general, the degree-constrained MST problem is NP-hard, but the unusual nature of the degree constraints here—every node either has degree 2 or unlimited degree—makes me hope that the there might still be an efficient algorithm. Are there any similar problems or algorithms that have been better studied?