Minimum Spanning Trees with Bounded Degrees of Vertices in a Specified Stable Set

Abstract

Given a graph $G$ and sets $\{\hat{I}{\pm }_v|v\in V(G)\}$ and $\{{\hat{I}}_v^2|v\in V(G)\}$ of non-negative integers, it is known that the decision problem whether $G$ contains a spanning tree $T$ such that $\hat{I}{\pm }_v\le d_T(v)\le {\hat{I}}_v^2$ for all $v\in V(G)$ is $NP$-complete. In this article, we relax the problem by demanding that the degree restrictions apply to vertices $v\in U$ only, where $U$ is a stable set of $G$. In this case, the problem becomes tractable. A. Frank presented a result characterizing the positive instances of that relaxed problem. Using matroid intersection developed by J. Edmonds, we give a new and short proof of Frank's result and show that if $U$ is stable and the edges of $G$ are weighted by arbitrary real numbers, then even a minimum-cost tree $T$ with $\hat{I}{\pm }_v\le d_T(v)\le {\hat{I}}_v^2$ for all $v\in U$ can be found in polynomial time if such a tree exists.