Generalized Bounded Tree Cover of a Graph

Abstract

A tree cover of a graph is a collection of subgraphs such that each vertex is a part of at least one subgraph and each subgraph is a tree. The bounded tree cover problem (BTC) finds a tree cover with minimum number of trees of bounded weight. This paper considers several generalized versions of BTC. The first problem deals with graphs having multiple metric weight functions. Strong and weak tree cover problems are two variations of the first problem. In strong tree cover, every tree must be bounded with respect to all weight functions, whereas in weak tree cover, each tree must be bounded with respect to at least one weight function. A 4-approximation algorithm for strong tree cover and an $O(\log n)$-approximation algorithm for weak tree cover problem are proposed. The objective of the second problem is to find a tree cover where bounds of the trees in the tree cover are not necessarily same. It is proved that this problem cannot be approximated within a constant factor unless P=NP. A constant factor approximation algorithm is proposed when the ratio of maximum and minimum bounds is bounded by a constant. The third problem considers BTC for a graph with a general weight function which is not necessarily metric. A 3-approximation algorithm is proposed for this problem.