Abstract
A subset M of vertices of a graph is called a static monopoly, if any vertex v outside M has at least \(\lceil \tfrac{1 }{2}\deg (v)\rceil \) neighbors in M. The minimum static monopoly problem has been extensively studied in graph theoretical context. We study this problem from an integer programming point of view for the first time and give a linear formulation for it. We study the facial structure of the corresponding polytope, classify facet defining inequalities of the integer programming formulation and introduce some families of valid inequalities. We show that in the presence of a vertex cut or an edge cut in the graph, the problem can be solved more efficiently by adding some strong valid inequalities. An algorithm is given that solves the minimum monopoly problem in trees and cactus graphs in linear time. We test our methods by performing several experiments on randomly generated graphs. A software package is introduced that solves the minimum monopoly problem using open source integer linear programming solvers.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Gurobi Optimization Inc., Gurobi Optimizer Reference Manual (2016), http://www.gurobi.com.
NETWORKX 1.11, High-productivity software for complex networks, https://networkx.github.io.
T. Christof, M. Stoer, and A. Loebel, PORTA - a polyhedron representation transformation algorithm, Version 1.3 (1997), http://www.iwr.uni-heidelberg.de/groups/comopt/software/PORTA.
CBC solver 2.9, Coin OR, https://projects.coin-or.org/Cbc.
CLP solver 1.16, Coin OR, https://projects.coin-or.org/Clp.
References
Ackerman E, Ben-Zwi O, Wolfovitz G (2010) Combinatorial model and bounds for target set selection. Theor Comput Sci 411(44–46):4017–4022. https://doi.org/10.1016/j.tcs.2010.08.021
Balas E, Ng SM (1989a) On the set covering polytope. I. All the facets with coefficients in \(\{0,1,2\}\). Math Program 43((1, (Ser. A))):57–69. https://doi.org/10.1007/BF01582278
Balas E, Ng SM (1989b) On the set covering polytope. II. Lifting the facets with coefficients in \(\{0,1,2\}\). Math Program 45((1, (Ser. B))):1–20. https://doi.org/10.1007/BF01589093
Bondy JA, Murty USR (2008) Graph theory. Graduate texts in mathematics. Springer, New York. https://doi.org/10.1007/978-1-84628-970-5
Cicalese F, Cordasco G, Gargano L, Milanič M, Peters J, Vaccaro U (2015) Spread of influence in weighted networks under time and budget constraints. Theor Comput Sci 586:40–58. https://doi.org/10.1016/j.tcs.2015.02.032
Cornuéjols G, Sassano A (1989) On the 0,1 facets of the set covering polytope. Math Program 43((1, (Ser. A))):45–55. https://doi.org/10.1007/BF01582277
Erdös P, Rényi A (1959) On random graphs. I. Publ Math Debr 6:290–297
Haynes TW, Hedetniemi ST, Slater PJ (1998) Fundamentals of domination in graphs. Monographs and textbooks in pure and applied mathematics, vol 208. Marcel Dekker Inc, New York
Hedetniemi ST, Laskar R, Pfaff J (1986) A linear algorithm for finding a minimum dominating set in a cactus. Discrete Appl Math 13(2–3):287–292. https://doi.org/10.1016/0166-218X(86)90089-2
Kempe D, Kleinberg J, Tardos E (2015) Maximizing the spread of influence through a social network. Theory Comput 11:105–147. https://doi.org/10.4086/toc.2015.v011a004
Khoshkhah K, Soltani H, Zaker M (2012) On dynamic monopolies of graphs: the average and strict majority thresholds. Discrete Optim 9(2):77–83, https://doi.org/10.1016/j.disopt.2012.02.001, http://www.sciencedirect.com/science/article/pii/S1572528612000151
Khoshkhah K, Nemati M, Soltani H, Zaker M (2013) A study of monopolies in graphs. Graphs Comb 29(5):1417–1427. https://doi.org/10.1007/s00373-012-1214-7
Korneyenko NM (1994) Combinatorial algorithms on a class of graphs. Discrete Appl Math 54(2–3):215–217. https://doi.org/10.1016/0166-218X(94)90022-1
Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0-1 optimization. SIAM J Optim 1(2):166–190. https://doi.org/10.1137/0801013
Markov M, Andreica MI, Manev K, Ţăpuş N (2012) A linear time algorithm for computing longest paths in cactus graphs. Serdica J Comput 6(3):287–298
Nemhauser G, Wolsey L (1999) Integer and combinatorial optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, reprint of the 1988 original, A Wiley-Interscience Publication
Sánchez-Garcí a M, Sobrón MI, Vitoriano B (1998) On the set covering polytope: facets with coefficients in \(\{0,1,2,3\}\). Ann Oper Res 81:343–356, https://doi.org/10.1023/A:1018969410431, applied mathematical programming and modeling, III (APMOD95) (Uxbridge)
Sassano A (1989) On the facial structure of the set covering polytope. Math Program 44((2, (Ser. A))):181–202. https://doi.org/10.1007/BF01587087
Sigarreta JM, Rodríguez JA (2009) On the global offensive alliance number of a graph. Discrete Appl Math 157(2):219–226. https://doi.org/10.1016/j.dam.2008.02.007
Soltani H, Zaker M (2014) Partial vertex cover and the complexity of some monopoly problems. to appear in Utilitas Mathematica
Zaker M (2012) On dynamic monopolies of graphs with general thresholds. Discrete Math 312(6):1136–1143. https://doi.org/10.1016/j.disc.2011.11.038
Acknowledgements
The authors are thankful for insightful comments from the anonymous referee that helped to improve the presentation of the results.
Author information
Authors and Affiliations
Corresponding author
Additional information
Babak Moazzez and Hossein Soltani are co-first authors and contributed equally to this work. The names of the authors are written in alphabetical order.
Rights and permissions
About this article
Cite this article
Moazzez, B., Soltani, H. Integer programming approach to static monopolies in graphs. J Comb Optim 35, 1009–1041 (2018). https://doi.org/10.1007/s10878-018-0256-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-018-0256-z