On the hardness and approximation of minimum topic-connected overlay

ABSTRACT

The design of a scalable overlay network to support decentralized topic-based publish/subscribe communication is nowadays a problem of a great importance. We investigate here special instances of one such design problem called Minimum Topic-Connected Overlay. Given a collection of 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. We investigate instances where in addition the number of users interested in a particular topic is bounded by a constant d > 2. It is known that the general Topic-Connected Overlay is Ω(log n) hard to approximate and approximable by a logarithmic factor. For our special instances, we design a one-to-one reduction to special instances of the hitting set problem. This allows us to present the first constant approximation algorithm, the first kernelization and the first nontrivial exact algorithm for the special instances discussed.

References

1. F. N. Abu-Khzam. Kernelization algorithms for d-hitting set problems. In Proc. of the 10th International Workshop on Algorithms and Data Structures (WADS 2007), volume 4619 of LNCS, pages 434--445. Springer-Verlag, 2007.
2. D. Angluin, J. Aspnes, and L. Reyzin. Inferring social networks from outbreaks. In Proc. of the 21st International Conference on Algorithmic Learning Theory (ALT 2010), pages 104--118, 2010.
3. G. Chockler, R. Melamed, Y. Tock, and R. Vitenberg. Constructing scalable overlays for pub-sub with many topics. In Proc. of the 26th Annual ACM Symposium on Principles of Distributed Computing (PODC 2007), pages 109--118. ACM, 2007.
4. S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2-epsilon. Journal of Computer and System Sciences, 74(3):335--349, 2008.
5. E. Korach and M. Stern. The clustering matroid and the optimal clustering tree. Mathematical Programming, 98(1-3):385--414, 2003.
6. E. Korach and M. Stern. The complete optimal stars-clustering-tree problem. Discrete Applied Mathematics, 156(4):444--450, 2008.
7. R. Niedermeier and P. Rossmanith. On efficient fixed-parameter algorithms for weighted vertex cover. Journal of Algorithms, 47(2):63--77, 2003.
8. M. Onus and A. W. Richa. Minimum maximum degree publish-subscribe overlay network design. In Proc. of IEEE INFOCOM 2009, pages 882--890. IEEE, 2009.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Network flows

• Networks

  • Network properties

    • Network structure

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows