6
$\begingroup$

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.

$\endgroup$

1 Answer 1

10
$\begingroup$

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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.