  In the context of designing a scalable overlay network to support
decentralized topic-based pub/sub communication, the Minimum Topic-Connected
Overlay problem (Min-TCO in short) has been investigated: Given a set of t
topics and a collection of n users together with the lists of topics they are
interested in, the aim is to connect these users to a network by a minimum
number of edges such that every graph induced by users interested in a common
topic is connected. It is known that Min-TCO is NP-hard and approximable within
O(log t) in polynomial time. In this paper, we further investigate the problem
and some of its special instances. We give various hardness results for
instances where the number of topics in which an user is interested in is
bounded by a constant, and also for the instances where the number of users
interested in a common topic is constant. For the latter case, we present a
first constant approximation algorithm. We also present some polynomial-time
algorithms for very restricted instances of Min-TCO.
