Finding subsets maximizing minimum structures

Abstract

We are interested in 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.1' 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 (remoteST), or Traveling Salesperson tour (Remote-TSP). We give: (1) iVP-hardness and lower bounds of approximation ratios of the above remote fe-set problems, (2) a tight performance ratio of 4 for a greedy algorithm for Remote-MST on metric graphs, (3) au improved approximation algorithm for Remote-MST with a performance ratio 2.25 for a graph induced from Euclidean distances of a set of points in a plane, and (4) corresponding results for Remote-ST and Remote-TSP problems.