×

On \(f\)-domination: polyhedral and algorithmic results. (English) Zbl 1419.05166

Summary: Given an undirected simple graph \(G\) with node set \(V\) and edge set \(E\), let \(f_v\), for each node \(v \in V\), denote a nonnegative integer value that is lower than or equal to the degree of \(v\) in \(G\). An \(f\)-dominating set in \(G\) is a node subset \(D\) such that for each node \(v\in V{{\setminus }}D\) at least \(f_v\) of its neighbors belong to \(D\). In this paper, we study the polyhedral structure of the polytope defined as the convex hull of all the incidence vectors of \(f\)-dominating sets in \(G\) and give a complete description for the case of trees. We prove that the corresponding separation problem can be solved in polynomial time. In addition, we present a linear-time algorithm to solve the weighted version of the problem on trees: Given a cost \(c_v\in{\mathbb{R}}\) for each node \(v\in V\), find an \(f\)-dominating set \(D\) in \(G\) whose cost, given by \(\sum _{v\in D}{c_v}\), is a minimum.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
51M20 Polyhedra and polytopes; regular figures, division of spaces
68Q25 Analysis of algorithms and problem complexity
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aoun B, Boutaba R, Iraqi Y, Kenward G (2006) Gateway placement optimization in wireless mesh networks with QoS constraints. IEEE J Sel Areas Commun 24(11):2127-2136 · doi:10.1109/JSAC.2006.881606
[2] Baïou M, Barahona F (2014) The dominating set polytope via facility location. In: ISCO 2014, LNCS 8596, pp 38-49 · Zbl 1452.90308
[3] Benzaken C, Hammer PL (1978) Linear separation of domination sets in graphs. Ann Discrete Math 3:1-10 · Zbl 0375.05043 · doi:10.1016/S0167-5060(08)70492-8
[4] Bermudo S, Hernandez-Gomez JC, Sigaretta JM (2018) On the total k-domination in graphs. Discuss Math Graph Theory 38:301-317 · Zbl 1377.05137 · doi:10.7151/dmgt.2016
[5] Bianchi S, Nasini G, Tolomei P (2010) The set covering problem on circulant matrices: polynomial instances and the relation with the dominating set problem on webs. Electronic Notes Discrete Math 36:1185-1192 · Zbl 1274.90448 · doi:10.1016/j.endm.2010.05.150
[6] Blum M, Floyd RW, Pratt V, Rivest RL, Tarjan RE (1973) Time bounds for selection. J Comput Syst Sci 7(4):448-461 · Zbl 0278.68033 · doi:10.1016/S0022-0000(73)80033-9
[7] Booth KS (1980) Dominating sets in chordal graphs. Technical Report CS-80-34. Univ. Waterloo, Waterloo, Ontario, Canada · Zbl 0485.05055
[8] Booth KS, Johnson JH (1982) Dominating sets in chordal graphs. SIAM J Comput 11:191-199 · Zbl 0485.05055 · doi:10.1137/0211015
[9] Bouamama S, Blum C (2016) A hybrid algorithmic model for the minimum weight dominating set problem. Simul Model Pract Theory 64:57-78 · doi:10.1016/j.simpat.2015.11.001
[10] Bouchakour M, Mahjoub AR (1997) One-node cutsets and the dominating set polytope. Discrete Math 165(166):101-123 · Zbl 0872.90104 · doi:10.1016/S0012-365X(96)00164-1
[11] Bouchakour M, Contenza TM, Lee CW, Mahjoub AR (2008) On the dominating set polytope. Eur J Comb 29:652-661 · Zbl 1168.05340 · doi:10.1016/j.ejc.2007.03.010
[12] Chen YP, Liestman AL (2002) Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks. In: Proceedings of the 3rd ACM international symposium on mobile ad hoc networking & computing (MobiHoc ’02), ACM, New York, pp 165-172
[13] Chen B, Zhou S (1998) Upper bounds for \[f\] f-domination number of graphs. Discrete Math 185:239-243 · Zbl 0955.05077 · doi:10.1016/S0012-365X(97)00204-5
[14] Chlebík M, Chlebíková J (2008) Approximation hardness of dominating set problems in bounded degree graphs. Inf Comput 206:1264-1275 · Zbl 1169.68037 · doi:10.1016/j.ic.2008.07.003
[15] Couture M, Barbeau M, Bose P, Kranakis E (2006) Incremental construction of \[k\] k-dominating sets in wireless sensor networks. In: Proceedings of the 10th international conference on principles of distributed systems, pp 202-214
[16] Chvátal V (1975) On certain polytopes associated with graphs. J Comb Theory (B) 18:138-154 · Zbl 0277.05139 · doi:10.1016/0095-8956(75)90041-6
[17] Dell’Amico M, Neto J (2017) On total \[f\] f-domination: polyhedral and algorithmic results. Technical report. University of Modena and Reggio Emilia, Italy · Zbl 1407.05175
[18] Duh R, Fürer M (1997) Approximation of \[k\] k-set cover by semi-local optimization. In: Proceedings of the 29th ACM symposium on theory of computing, STOC, pp 256-264 · Zbl 0962.68172
[19] Farber M (1984) Domination, independent domination, and duality in strongly chordal graphs. Discrete Appl Math 7:115-130 · Zbl 0531.05045 · doi:10.1016/0166-218X(84)90061-1
[20] Foerster KT (2013) Approximating fault-tolerant domination in general graphs. In: Proceedings of the tenth workshop on analytic algorithmics and combinatorics (ANALCO), pp 25-32 · Zbl 1430.68200
[21] Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco · Zbl 0411.68039
[22] Grötschel M, Lovàsz L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169-197 · Zbl 0492.90056 · doi:10.1007/BF02579273
[23] Hammer PL, Johnson EL, Peled UN (1975) Facet of regular 0-1 polytopes. Math Program 8:179-206 · Zbl 0314.90064 · doi:10.1007/BF01580442
[24] Haynes TW, Hedetniemi ST, Slater JB (1998a) Fundamentals of domination in graphs. Marcel Dekker, New York City · Zbl 0890.05002
[25] Haynes TW, Hedetniemi ST, Slater JB (1998b) Domination in graphs: advanced topics. Marcel Dekker, New York City · Zbl 0883.00011
[26] Hedetniemi S, Hedetniemi S, Laskar R (1985) Domination in trees: models and algorithms. Graph theory with applications to algorithms and computer science. Wiley, New York, pp 423-442 · Zbl 0575.05022
[27] Hedetniemi ST, Laskar R, Pfaff J (1986) A linear algorithm for finding a minimum dominating set in a cactus. Discrete Appl Math 13:287-292 · Zbl 0596.05051 · doi:10.1016/0166-218X(86)90089-2
[28] Henning M, Yeo A (2013) Total domination in graphs. Springer monographs in mathematics. Springer, Berlin · Zbl 1408.05002 · doi:10.1007/978-1-4614-6525-6
[29] Houmaidi ME, Bassiouni MA (2003), K-weighted minimum dominating sets for sparse wavelength converters placement under non-uniform traffic. In: Proceedings of MASCOTS’03, pp 56-61
[30] Hwang SF, Chang GJ (1991) The \[k\] k-neighbor domination problem. Eur J Oper Res 52:373-377 · Zbl 0734.90045 · doi:10.1016/0377-2217(91)90172-R
[31] Kikuno T, Yoshida N, Kakuda Y (1983) A linear algorithm for the domination number of a series-parallel graph. Discrete Appl Math 5:299-311 · Zbl 0507.05060 · doi:10.1016/0166-218X(83)90003-3
[32] Mahjoub AR (1983) Le polytope des absorbants dans une classe de graphe à seuil. Ann Discrete Math 17:443-452 · Zbl 0543.05050
[33] Natarajan KS, White LJ (1978) Optimum domination in weighted trees. Inf Process Lett 7(6):261-265 · Zbl 0391.05046 · doi:10.1016/0020-0190(78)90012-1
[34] Nemhauser GL, Trotter LE (1974) Properties of vertex packing and independence system polyhedra. Math Program 6:48-61 · Zbl 0281.90072 · doi:10.1007/BF01580222
[35] Padberg MW (1974) Perfect zero-one matrices. Math Program 6:180-196 · Zbl 0284.90061 · doi:10.1007/BF01580235
[36] Potluri A, Singh A (2013) Hybrid metaheuristic algorithms for minimum weight dominating set. Appl Soft Comput 13:76-88 · doi:10.1016/j.asoc.2012.07.009
[37] Shen C, Li T (2010) Multi-document summarization via the minimum dominating set. In: Proceedings of the 23rd international conference on computational linguistics, pp 984-992
[38] Stracke C, Volkmann L (1993) A new domination conception. J Graph Theory 17:315-323 · Zbl 0777.05074 · doi:10.1002/jgt.3190170306
[39] Subhadrabandhu D, Sarkar S, Anjum F (2004) Efficacy of misuse detection in adhoc networks. In: Proceedings of the first annual IEEE communications society conference on sensor and ad hoc communications and networks, pp 97-107
[40] Wu J, Li H (1999) On calculating connected dominating set for efficient routing in ad-hoc wireless networks. In: Proceedings of DIALM ’99, ACM, New York, pp 7-14
[41] Wu P, Wen JR, Liu H, Ma WY (2006) Query selection techniques for efficient crawling of structured web sources. Proceedings of ICDE’06, pp 47
[42] Zhou SM (1996) On \[f\] f-domination number of a graph. Czechoslov Math J 46(3):489-499 · Zbl 0879.05037
[43] Zou F, Wang Y, Xu X, Li X, Du H, Wan P, Wu W (2011) New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theor Comp Sci 412:198-208 · Zbl 1209.68389 · doi:10.1016/j.tcs.2009.06.022
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.