We provide new non-approximability results for the restrictions of the min-VC problem to bounded-degree, sparse and dense graphs. We show that for a sufficiently large B, the recent 16/15 lower bound proved by Bellare et al. extends with negligible loss to graphs with bounded degree B. Then, we consider sparse ... more >>>

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of Aingworth, Chekuri and Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time ... more >>>