Finding subsets maximizing minimum structures

Abstract

We consider the problem of finding a set of k vertices in a graph that are in some sense remote. Stated more formally, given a graph G and an integer k, find a set P of k vertices for which the total weight of a minimum structure on P is maximized. In particular, we are interested in three problems of this type, where the structure to be minimized is a spanning tree (REMOTE-MST), Steiner tree, or traveling salesperson tour. We study a natural greedy algorithm that simultaneously approximates all three problems on metric graphs. For instance, its performance ratio for REMOTE-MST is exactly 4, while this problem is N P-hard to approximate within a factor of less than 2. We also give a better approximation for graphs induced by Euclidean points in the plane, present an exact algorithm for graphs whose distances correspond to shortest-path distances in a tree, and prove hardness and approximability results for general graphs.