Abstract
We study local, distributed algorithms for the capacitated minimum dominating set (CapMDS) problem, which arises in various distributed network applications. Given a network graph G=(V,E), and a capacity cap(v)∈ℕ for each node v∈V, the CapMDS problem asks for a subset S⊆V of minimal cardinality, such that every network node not in S is covered by at least one neighbor in S, and every node v∈S covers at most cap(v) of its neighbors. We prove that in general graphs and even with uniform capacities, the problem is inherently non-local, i.e., every distributed algorithm achieving a non-trivial approximation ratio must have a time complexity that essentially grows linearly with the network diameter. On the other hand, if for some parameter ε>0, capacities can be violated by a factor of 1+ε, CapMDS becomes much more local. Particularly, based on a novel distributed randomized rounding technique, we present a distributed bi-criteria algorithm that achieves an O(log Δ)-approximation in time O(log 3 n+log (n)/ε), where n and Δ denote the number of nodes and the maximal degree in G, respectively. Finally, we prove that in geometric network graphs typically arising in wireless settings, the uniform problem can be approximated within a constant factor in logarithmic time, whereas the non-uniform problem remains entirely non-local.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567–583 (1986)
Alzoubi, K., Wan, P.-J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: Proc. of the 3rd ACM Int. Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), EPFL Lausanne, Switzerland, pp. 157–164 (2002)
Awerbuch, B.: Complexity of network synchronization. J. ACM 32(4), 804–823 (1985)
Bar-Ilan, J., Kortsarz, G., Peleg, D.: How to allocate network centers. J. Algorithms 15(3), 385–415 (1993)
Bar-Ilan, J., Kortsarz, G., Peleg, D.: Generalized submodular cover problems and applications. Theor. Comput. Sci. 250, 179–200 (2001)
Birk, Y., Keidar, I., Liss, L., Schuster, A., Wolff, R.: Veracity radius—capturing the locality of distributed computations. In: Proc. of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2006)
Chan, H., Luk, M., Perrig, A.: Using clustering information for sensor network localization. In: Proc. of the 1st Conference on Distributed Computing in Sensor Systems (DCOSS) (2005)
Dai, F., Wu, J.: An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. Parallel Distrib. Syst. 15(10), 902–920 (2004)
Deb, B., Nath, B.: On the node-scheduling approach to topology control in ad hoc networks. In: Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 14–26 (2005)
Elkin, M.: Distributed approximation—a survey. ACM SIGACT News—Distrib. Comput. Column 35(4), 40–57 (2004)
Gandhi, R., Parthasarathy, S.: Distributed algorithms for coloring and connected domination in wireless ad hoc networks. In: Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (2004)
Gao, J., Guibas, L., Hershberger, J., Zhang, L., Zhu, A.: Discrete mobile centers. In: Proc. 17th Symposium on Computational Geometry (SCG), pp. 188–196 (2001)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Gfeller, B., Vicari, E.: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In: Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC), pp. 53–60 (2007)
Grandoni, F., Krönemann, J., Panconesi, A., Sozio, M.: Primal-dual based distributed algorithms for vertex cover with semi-hard capacities. In: Proc. of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 118–125 (2005)
Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS), p. 8020. IEEE Comput. Soc., Los Alamitos (2000)
Jia, L., Rajaraman, R., Suel, R.: An efficient distributed algorithm for constructing small dominating sets. In: Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pp. 33–42 (2001)
Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 300–309 (2004)
Kuhn, F., Moscibroda, T., Wattenhofer, R.: The locality of bounded growth. In: Proc. of the 24th ACM Symp. on Principles of Distributed Computing (PODC) (2005)
Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA) (2006)
Kuhn, F., Moscriboda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Proc. 19th Symposium on Distributed Computing (DISC) (2005)
Kuhn, F., Wattenhofer, R.: Constant-time distributed dominating set approximation. Distrib. Comput. J. 17(4), 303–310 (2005)
Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J. Algorithms 28, 40–66 (1998)
Lenzen, C., Wattenhofer, R.: Leveraging Linial’s locality limit. In: Proc. of 22nd Symposium on Distributed Computing (DISC), Arcachon, France, September 2008
Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)
Linial, N., Saks, M.: Low diameter graph decompositions. Combinatorica 13(4), 441–454 (1993)
Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 1036–1053 (1986)
Moscibroda, T., Wattenhofer, R.: Maximal independent sets in radio networks. In: Proc. of the 23rd ACM Symp. on Principles of Distributed Computing (PODC) (2005)
Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259–1277 (1995)
Raghavan, P., Thompson, C.D.: Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365–374 (1987)
Schneider, J., Wattenhofer, R.: A log-star distributed maximal independent set algorithm for growth-bounded graphs. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC) (2008)
Wan, P., Alzoubi, K., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. In: Proceedings of INFOCOM (2002)
Wang, Y., Wang, W., Li, X.-Y.: Distributed low-cost backbone formation for wireless ad hoc networks. In: Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 2–13 (2005)
Wu, J., Li, H.: On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proc. of the 3rd Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pp. 7–14 (1999)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper has appeared in the Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego, California, USA, June 2007.
Rights and permissions
About this article
Cite this article
Kuhn, F., Moscibroda, T. Distributed Approximation of Capacitated Dominating Sets. Theory Comput Syst 47, 811–836 (2010). https://doi.org/10.1007/s00224-010-9271-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-010-9271-x