# Finding appropriate spanning tree of connected bipartite graph

I got this as a sub-problem while working on a research problem connected to index coding. Can someone please give me directions as to how to approach this problem?

Problem: We have a connected undirected bipartite graph $G=(U,V,E)$. Let $|U| = m$ and the degree of $i$th node in U be $a_i$. Consider a spanning tree of $G$ and let the degree of $i$th node in $U$ be $b_i$ in the spanning tree (so $b_i \le a_i$). I am interested in finding the spanning tree that minimizes $max_{i=1,2,...,m} (a_i-b_i)$. I am interested in getting directions about how to design an algorithm for it.

Isn't this a special case of matroid intersection, which is solvable in polynomial time?

Fix your graph $G$ and any integer $d \in \{0,1,\ldots,\max_i a_i\}$. You want to maximize $d$; you can try all possibilities. For a given $d$, you want to answer the following question:

Is there is a spanning tree $T$ such that $\max_i a_i - \mbox{deg}_T(u_i) \le d$?

Since any spanning tree has $n-1$ edges, the following question is equivalent:

Is there an edge-set $S$ of size at least $|E|-n+1$, with at most $d$ edges incident to each vertex in $U$, whose complement contains a spanning tree?

Thus, your problem reduces to the following problem:

Find a maximum-size edge-set $S$ having at most $d$ edges incident to each vertex in $U$ and whose complement contains a spanning tree.

The independent sets of edges in $G$ form a matroid. The bases are the spanning trees. The dual of this matroid is a matroid $M_t^*$. The edge-sets in $M_t^*$ are the edge-sets whose complement contains a spanning tree.

The edge-sets in which each vertex $u_i$ in $U$ has degree at most $d$ form yet another matroid $M_d$.

Thus, the following two conditions on edge-set $S$ are equivalent:

1. $S$ is in the intersection $M_d \cap M_t^*$ of the two matroids;

2. $S$ has at most $d$ edges incident to each vertex in $U$, and the complement of $S$ contains a spanning tree.

So the following algorithm solves the problem in polynomial time:

Using matroid intersection, find a maximum-size edge-set $S$ in $M_d \cap M^*_t$.