Group for Research in Decision Analysis

On the Optimal Clustering Tree Problem

Ephraim Korach

The Optimal Clustering Tree problem is: let \(G=(V,E)\) be a complete graph with a cost function on its edges and let \(S\) be a given collection of subsets of \(V\). A spanning tree \(T\) is called a clustering tree (relative to \(S\)) if each subset of the vertices in S induces a subtree in \(T\). Our problem is to find a minimum cost clustering tree \(T\). We call this problem the OP problem. One motivation for this problem is to construct a minimum cost communication tree network for a collection of non-disjoint groups of customers such that the network will provide “group fault tolerance” and “group privacy”. We present some results on this problem and also on some variations of it. The first variation we consider is the clustering-TSP-path problem. In this case the input is the same as the input of the general problem. However, the tree that we would like to construct is a minimum cost TSP path. The problem in general is NP-hard and we solve some restricted cases. The second variation is the stars-OP problem, where again the input is the same as the input of the general problem. However, in this case we would like to construct a tree such that each subset induces a subtree that is a complete star. For this case we have proved a structure theorem that leads to a polynomial algorithm. A Dynamic programming polynomial algorithm for another variation of the Stars-OP is presented.

The latter problems have possible applications in robotics, in databases with synchronous replications and in the area of key management for secure group communication.

Joint work with Michal Stern.