On the TSP and related problems – 2

3. k-MST: (general (as opposed to metric) version) :- Given an undirected graph $G= (V,E)$, with non-negative edge lengths $l : E \rightarrow \mathbb{R}^{+}$, find a tree of minimum length that spans at least $k$ vertices.

Notes on the k-MST problem:

• There are two versions of the k-MST problem. The rooted version specifies a root vertex, r, which must necessarily be included in the tree. The unrooted version does not place any such restriction.
• An $\alpha$-approximation algorithm for unrooted k-MST gives an $\alpha$-approximation algorithm for rooted k-MST. Consider an instance of rooted k-MST. Add |V| additional vertices to G, and an edge of zero length between the root and each of them. Clearly, an optimal solution of the unrooted version requiring the tree to span at least |V| + k vertices in the reduced instance, is an optimal solution for the rooted version for k vertices. Hence, an $\alpha$-approximation algorithm for unrooted k-MST implies an $\alpha$-approximation algorithm for rooted k-MST.
• An $\alpha$-approximation algorithm for rooted k-MST gives an $\alpha$-approximation algorithm for unrooted k-MST. Consider an instance of unrooted k-MST. Run the $\alpha$-approximation algorithm for rooted k-MST on all vertices. The least cost solution among these gives an $\alpha$-approximate solution to the unrooted version. ( The least cost optimal solution over all vertices (as roots) for the rooted version is an optimal solution for the unrooted version. Hence, the least cost $\alpha$-approximate solution over all vertices for the rooted version gives a solution that is within $\alpha$-factor of the optimal for the unrooted version.)
• Budget version of k-MST: Given an undirected graph $G= (V,E)$, a non-negative length function $l : E \rightarrow \mathbb{R}^{+}$, and a budget $B$, find a tree that spans the maximum number of vertices subject to the condition that the length of the tree is at most the upper bound $B$.
• Garg [2005] gave a 2-approximation algorithm for k-MST.
• Metric version of k-MST: Given an n-vertex metric space, $(V,d)$, and a number k, find a minimum length tree that spans at least k vertices.

4. k-forest: Given an undirected graph $G= (V,E)$ with non-negative length function $l : E \rightarrow \mathbb{R}^{+}$, a set of $m$ demand pairs $\{s_i, t_i\}_{i=1}^{m} \subset V \times V$, and a number k, find a least cost subgraph that connects (satisfies) at least $k$ demand pairs.

• Rooted k-MST reduces to k-forest. (k-forest generalizes rooted k-MST.) Consider a rooted k-MST instance on $G= (V,E)$ with root $r$. Fix $|V| - 1$ demand pairs $\{r,v\}$ where $v \in V - \{r\}$. An optimal solution satisfying $k-1$ demand pairs in this reduced instance is also an optimal solution for rooted k-MST on the original instance. Also, clearly, an $\alpha$-approximation algorithm for k-forest gives an $\alpha$-approximation algorithm for rooted k-MST.
• Unrooted k-MST reduces in polynomial time to k-forest. This follows from the reductions from the unrooted k-MST to rooted k-MST, and from rooted k-MST to k-forest. Again, an $\alpha$-approximation algorithm for k-forest gives an $\alpha$-approximation algorithm for unrooted k-MST.
• Metric k-forest: Given an n-vertex metric space $(V,d)$, a set of $m$ demand pairs $\{s_i, t_i\}_{i=1}^{m} \subset V \times V$, and a number $k$, find a least cost subgraph satisfying at least $k$ demand pairs.
• Metric versions of rooted and unrooted k-MST reduce in polynomial time to metric k-forest.

References:

• Naveen Garg: Saving an epsilon: A 2-approximation for the k-MST problem in graphs, 2005.