<p>Isn't this a special case of matroid intersection,
which is <a href="http://en.wikipedia.org/wiki/Matroid#Matroid_intersection">solvable in polynomial time</a>?</p>

<p>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:</p>

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

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

<blockquote>
  <p><em>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?</em></p>
</blockquote>

<p>Thus, your problem reduces to the following problem:</p>

<blockquote>
  <p><em>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.</em></p>
</blockquote>

<p>The independent sets of edges in $G$ form a matroid.  The bases are the spanning trees.  The <a href="http://en.wikipedia.org/wiki/Matroid#Duality">dual</a> of this matroid is a matroid $M_t^*$.  The edge-sets in $M_t^*$ are the edge-sets whose complement contains a spanning tree.</p>

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

<p>Thus, the following two conditions on edge-set $S$ are equivalent:</p>

<ol>
<li><p>$S$ is in the intersection $M_d \cap M_t^*$ of the two matroids;</p></li>
<li><p>$S$ has at most $d$ edges incident to each vertex in $U$, and the complement of $S$ contains a spanning tree.</p></li>
</ol>

<p>So the following algorithm solves the problem in polynomial time:</p>

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

CC BY-SA 3.0
2013-03-18T00:08:08.693Z
2013-03-18T00:19:20.890Z
2013-03-18T00:19:20.890Z
Neal Young
<p>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?</p>

<p>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.   </p>

<graph-theory><graph-algorithms><approximation-algorithms>
Finding appropriate spanning tree of connected bipartite graph
fenrir
# Finding appropriate spanning tree of connected bipartite graph

(Asked by: username_0 on 2013-03-17)

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.

**Tags:** graph-theory, graph-algorithms, approximation-algorithms

---

## 1 answers

### Answer by username_1 on 2013-03-18. Score: 10 | Accepted answer

Isn't this a special case of matroid intersection,
which is [solvable in polynomial time](http://en.wikipedia.org/wiki/Matroid#Matroid_intersection)?

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](http://en.wikipedia.org/wiki/Matroid#Duality) 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$.


---

