Computer Science/Discrete Mathematics Seminar I

Consider the minimum cost spanning tree problem under the restriction that all degrees must be at most a given value $k$. The main result I will present is that one can efficiently find a spanning tree of maximum degree at most $k+2$ whose cost is at most the cost of the optimum spanning tree of maximum degree $k$. This is almost best possible, as the problem of just deciding whether a graph has a spanning tree of maximum degree $k$ is NP-complete. The approach uses a sequence of simple algebraic, polyhedral and combinatorial arguments. It illustrates many techniques and ideas in combinatorial optimization as it involves polyhedral characterizations, uncrossing, matroid intersection, and graph orientations (or packing of spanning trees). The result generalizes to the setting where every vertex has both upper and lower bounds and gives then a spanning tree which violates the bounds by at most 2 units and whose cost is at most the cost of the optimum tree. Our approach also shows that any convex combination of spanning trees can be rewritten as a convex combination of spanning trees such that, for every vertex, its degree in every spanning tree is within 2 units of its average degree. The result also gives a better understanding of the subtour relaxation for both the symmetric and asymmetric traveling salesman problems.