TY - JOUR

T1 - On the approximability and hardness of minimum topic connected overlay and its special instances

AU - Hosoda, Jun

AU - Hromkovič, Juraj

AU - Izumi, Taisuke

AU - Ono, Hirotaka

AU - Steinová, Monika

AU - Wada, Koichi

N1 - Funding Information:
✩ This research is partly supported by the Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, 21500013, 21680001, 22650004, 22700010, 23104511, 23310104, Foundation for the Fusion of Science and Technology (FOST) and INAMORI FOUNDATION. The research is also partially funded by SNF grant 200021-132510/1. ✩✩ Some of the results of this paper were presented at MFCS 2011 and PODC 2011. ∗ Corresponding author. E-mail addresses: juraj.hromkovic@inf.ethz.ch (J. Hromkovič), t-izumi@nitech.ac.jp (T. Izumi), hirotaka@en.kyushu-u.ac.jp (H. Ono), monika.steinova@inf.ethz.ch (M. Steinová), wada@nitech.ac.jp (K. Wada).

PY - 2012/4/20

Y1 - 2012/4/20

N2 - 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(logt) 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 a 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 a 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.

AB - 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(logt) 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 a 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 a 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.

UR - http://www.scopus.com/inward/record.url?scp=84858340396&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84858340396&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2011.12.033

DO - 10.1016/j.tcs.2011.12.033

M3 - Article

AN - SCOPUS:84858340396

VL - 429

SP - 144

EP - 154

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -