Degree-bounded spanning trees and matroids

Speaker(s)

Attila Bernáth

Affiliation

Uniwersytet Warszawski

Date

Oct. 20, 2011, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Consider the problem of finding a minimum cost spanning tree in a graph with the additional requirement that the degree of each node in the tree should not exceed an upper bound given in advance. This problem is hard: already the problem of deciding whether such a tree exists is NP-complete, so it does not really make sense to speak about an approximation algorithm.
Therefore we relax the feasibility: we allow a small excess to the degree bounds. Interestingly enough, we only need to excess the degree bounds by 1, and the cost of our solution will not be worse than the cost of the optimal solution to the original problem (i.e. we do not have to relax the optimality, unlike it is done with usual approximation algorithms). I would like to present this result and a matroidal generalization of it. The results are due to Tamás Király, Lap Chi Lau and Mohit Singh.

---