×

On connected dominating sets of restricted diameter. (English) Zbl 1317.90303

Summary: A connected dominating set (CDS) is commonly used to model a virtual backbone of a wireless network. To bound the distance that information must travel through the network, we explicitly restrict the diameter of a CDS to be no more than \(s\) leading to the concept of a dominating \(s\)-club. We prove that for any fixed positive integer \(s\) it is NP-complete to determine if a graph has a dominating \(s\)-club, even when the graph has diameter \(s+1\). As a special case it is NP-complete to determine if a graph of diameter two has a dominating clique. We then propose a compact integer programming formulation for the related minimization problem, enhance the approach with variable fixing rules and valid inequalities, and present computational results.

MSC:

90C35 Programming involving graphs or networks
90B18 Communication networks in operations research
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alber, J.; Fellows, M.; Niedermeier, R., Polynomial-time data reduction for dominating set, Journal of the ACM, 51, 3, 363-384 (2004) · Zbl 1192.68337
[2] Alon, N.; Moshkovitz, D.; Safra, S., Algorithmic construction of sets for \(k\)-restrictions, ACM Transactions on Algorithms, 2, 2, 153-177 (2006) · Zbl 1321.68445
[3] Bacsó, G., Complete description of forbidden subgraphs in the structural domination problem, Discrete Mathematics, 309, 8, 2466-2472 (2009) · Zbl 1210.05093
[4] Bacsó, G.; Tuza, Z., Dominating cliques in \(P_5\)-free graphs, Periodica Mathematica Hungarica, 21, 4, 303-308 (1990) · Zbl 0746.05065
[5] Bacsó, G.; Tuza, Z., Dominating subgraphs of small diameter, Journal of Combinatorics, Information and System Sciences, 22, 1, 51-62 (1997) · Zbl 0913.90257
[6] Balasundaram, B.; Butenko, S.; Trukhanov, S., Novel approaches for analyzing biological networks, Journal of Combinatorial Optimization, 10, 1, 23-39 (2005) · Zbl 1080.90010
[7] Bourjolly, J.; Laporte, G.; Pesant, G., An exact algorithm for the maximum \(k\)-club problem in an undirected graph, European Journal of Operational Research, 138, 1, 21-28 (2002) · Zbl 1008.90048
[8] Brandstädt, A.; Kratsch, D., On the restriction of some NP-complete graph problems to permutation graphs, (Fundamentals of Computation Theory (1985), Springer), 53-62
[9] Brandstädt, A.; Kratsch, D., On domination problems for permutation and other graphs, Theoretical Computer Science, 54, 2-3, 181-198 (1987) · Zbl 0641.68100
[10] Butenko, S.; Cheng, X.; Oliveira, C.; Pardalos, P. M., A new heuristic for the minimum connected dominating set problem on ad hoc wireless networks, (Butenko, S.; Murphey, R.; Pardalos, P., Recent developments in cooperative control and optimization (2004), Kluwer Academic Publishers), 61-73
[11] Cheng, X.; Huang, X.; Li, D.; Wu, W.; Du, D.-Z., A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks, Networks, 42, 4, 202-208 (2003) · Zbl 1031.05092
[12] Cozzens, M.; Kelleher, L., Dominating cliques in graphs, Discrete Mathematics, 86, 1-3, 101-116 (1990) · Zbl 0722.05040
[13] Fan, N.; Watson, J.-P., Solving the connected dominating set problem and power dominating set problem by integer programming, (Lin, G., Combinatorial optimization and applications. Combinatorial optimization and applications, Lecture Notes in Computer Science, Vol. 7402 (2012), Springer: Springer Berlin/Heidelberg), 371-383 · Zbl 1358.05214
[14] Fernau, H.; Kneis, J.; Kratsch, D.; Langer, A.; Liedloff, M.; Raible, D., An exact algorithm for the Maximum Leaf Spanning Tree problem, Theoretical Computer Science, 412, 45, 6290-6302 (2011) · Zbl 1233.68236
[15] Fomin, F.; Grandoni, F.; Kratsch, D., Solving connected dominating set faster than \(2^n\), Algorithmica, 52, 2, 153-166 (2008) · Zbl 1170.68030
[16] Fujie, T., An exact algorithm for the maximum leaf spanning tree problem, Computers & Operations Research, 30, 13, 1931-1944 (2003) · Zbl 1047.90056
[17] Fujie, T., The maximum-leaf spanning tree problem: Formulations and facets, Networks, 43, 4, 212-223 (2004) · Zbl 1053.90098
[18] Guha, S.; Khuller, S., Approximation algorithms for connected dominating sets, Algorithmica, 20, 4, 374-387 (1998) · Zbl 0895.68106
[19] Haynes, T.; Hedetniemi, S.; Slater, P., Fundamentals of Domination in Graphs (1998), CRC Press · Zbl 0890.05002
[20] Hunt III, H. B.; Marathe, M.; Radhakrishnan, V.; Ravi, S.; Rosenkrantz, D.; Stearns, R., NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms, 26, 238-274 (1998) · Zbl 0894.68105
[21] Keil, J., The complexity of domination problems in circle graphs, Discrete Applied Mathematics, 42, 1, 51-63 (1993) · Zbl 0786.05079
[22] Kim, D.; Wu, Y.; Li, Y.; Zou, F.; Du, D.-Z., Constructing minimum connected dominating sets with bounded diameters in wireless networks, IEEE Transactions on Parallel and Distributed Systems, 20, 2, 147-157 (2009)
[23] Kratsch, D., Finding dominating cliques efficiently in strongly chordal graphs and undirected path graphs, Discrete Mathematics, 86, 1-3, 225-238 (1990) · Zbl 0729.05046
[24] Kratsch, D.; Liedloff, M., An exact algorithm for the minimum dominating clique problem, Theoretical Computer Science, 385, 1-3, 226-240 (2007) · Zbl 1125.68135
[25] Lucena, A.; Maculan, N.; Simonetti, L., Reformulations and solution algorithms for the maximum leaf spanning tree problem, Computational Management Science, 7, 3, 289-311 (2010) · Zbl 1198.90380
[26] Lu, H.; Ravi, R., Approximating maximum leaf spanning trees in almost linear time, Journal of Algorithms, 29, 1, 132-141 (1998) · Zbl 0919.68097
[27] Mohammed, K.; Gewali, L.; Muthukumar, V., Generating quality dominating sets for sensor network, (Proceedings of the sixth international conference on computational intelligence and multimedia applications (2005), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 204-211
[28] Mokken, R., Cliques, clubs and clans, Quality & Quantity, 13, 2, 161-173 (1979)
[29] Pattillo, J.; Youssef, N.; Butenko, S., On clique relaxation models in network analysis, European Journal of Operational Research, 226, 1, 9-18 (2013) · Zbl 1292.05208
[30] Raz, R.; Safra, S., A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, (Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (1997), ACM), 475-484 · Zbl 0963.68175
[31] Schaudt, O., On dominating sets whose induced subgraphs have a bounded diameter, Discrete Applied Mathematics, 161, 2647-2652 (2013) · Zbl 1285.05145
[32] Simonetti, L.; Salles da Cunha, A.; Lucena, A., The minimum connected dominating set problem: formulation, valid inequalities and a branch-and-cut algorithm, (Pahl, J.; Reiners, T.; Voss, S., Network Optimization. Network Optimization, Lecture notes in computer science, Vol. 6701 (2011), Springer: Springer Berlin/Heidelberg), 162-169, (ISBN 978-3-642-21526-1) · Zbl 1345.90102
[33] Tuza, Z., Hereditary domination in graphs: Characterization with forbidden induced subgraphs, SIAM Journal on Discrete Mathematics, 22, 3, 849-853 (2008) · Zbl 1181.05074
[34] Veremyev, A.; Boginski, V., Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems, European Journal of Operational Research, 218, 2, 316-326 (2012) · Zbl 1244.90201
[35] Yuan, D., Energy-efficient broadcasting in wireless ad hoc networks: performance benchmarking and distributed algorithms based on network connectivity characterization, (Proceedings of the 8th ACM international symposium on modeling, analysis and simulation of wireless and mobile systems (2005), ACM), 28-35
[36] Zhang, Z.; Gao, X.; Wu, W.; Du, D.-Z., PTAS for minimum connected dominating set in unit ball graph, (Li, Y.; Huynh, D.; Das, S.; Du, D.-Z., Wireless algorithms, systems, and applications. Wireless algorithms, systems, and applications, Lecture Notes in Computer Science, Vol. 5258 (2008), Springer: Springer Berlin/Heidelberg), 154-161, (ISBN 978-3-540-88581-8)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.