# Unusual MST variant on bipartite graph

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?

The problem is $$\mathsf{NP}$$-hard. We will show a reduction from the Hamiltonian path problem on general graphs.

Let $$G = (V,E)$$ be any hard instance of the Hamiltonian path problem.

Reduction: For every edge $$e = (u,v)$$ in $$E$$, create a new vertex $$x_{e}$$. Replace edge $$e$$ with two new edges $$(u,x_e)$$ and $$(x_e,v)$$. Furthermore, create a new vertex $$x_{v}$$ corresponding to every vertex $$v \in V$$ and add the edge $$(v,x_v)$$. Let $$N$$ denote the set of all new vertices added. Note that the new graph is a bipartite graph, with partitions $$N$$ and $$V$$. Assign each edge of the graph a unit weight. Here $$B = V$$. It is easy to see that this graph satisfies $$|N| \geq |B|+1$$. Also, every vertex in $$B$$ has degree at least $$2$$.

Claim: There exists a hamiltonian path in $$G$$ if and only if the bipartite graph has a subtree of weight $$2|B|$$ in which every vertex in $$B$$ has degree exactly $$2$$.

Proof: (->) Suppose $$h: (v_1,\dotsc,v_n)$$ be the hamiltonian path in graph $$G$$. Let $$e_{i}$$ denote the edge $$(v_{i},v_{i+1})$$ in $$h$$. Then, $$(x_{v_{1}},v_{1},x_{e_{1}},v_{2},\dotsc,v_{n-1},x_{e_{n-1}},v_{n},x_{n})$$ forms a subtree of weight $$2|B|$$ in the bipartite graph such that each vertex in $$B$$ has degree exactly $$2$$.

(<-) Suppose that there exists a subtree $$T$$ in the bipartite graph of weight $$2|B|$$ in which every vertex in $$B$$ has degree exactly $$2$$. Then, this subtree contains all vertices of $$B$$; otherwise, the weight of the subtree would have been less than $$2|B|$$. Also, note that the degree of every vertex in $$N$$ is either $$2$$ or $$1$$. Therefore, the degree of each vertex in $$T$$ is either $$1$$ or $$2$$. Therefore, $$T$$ must be a simple path with its vertices alternating between $$V$$ and $$B$$. Suppose this path is $$(x_{1},v_{1},x_{2},v_{2},\dotsc,v_{n-1},x_{n},v_{n},x_{n+1})$$. Then, this path corresponds to a hamiltonian path $$(v_1,\dotsc,v_n)$$ in the original graph $$G$$.

• OK, this solves the maximum subtree problem. What if we allow disconnected (but still acyclic) forests? The reduction from Hamiltonian path doesn't seem to work in that case. Sep 22 '21 at 0:43
• @Connor Right. Will also think about that. Sep 22 '21 at 13:10
• @Connor You found the solution or what? Sep 26 '21 at 2:39
• Not yet, but it seems unlikely that there will be a better answer. Sep 26 '21 at 13:10