Integer programming approach to static monopolies in graphs

Babak Moazzez () and Hossein Soltani ()
Additional contact information
Babak Moazzez: Kennesaw State University
Hossein Soltani: Urmia University of Technology

Journal of Combinatorial Optimization, 2018, vol. 35, issue 4, No 2, 1009-1041

Abstract: 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 $$ ⌈ 1 2 deg ( v ) ⌉ 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.

Keywords: Static monopoly; Integer programming; Polytopes; Valid inequalities; Cactus graphs; Majority thresholds; 05C69; 05C85; 90C10; 90C57 (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0256-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:35:y:2018:i:4:d:10.1007_s10878-018-0256-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0256-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().