Makino, Kazuhisa; Yamashita, Masafumi; Kameda, Tiko Max- and Min-neighborhood monopolies. (English) Zbl 1016.68057 Algorithmica 34, No. 3, 240-260 (2002). Summary: Given a graph \(G=(V,E)\) and a set of vertices \(M\subseteq V\), a vertex \(v\in V\) is said to be controlled by \(M\) if the majority of \(v\)’s neighbors (including itself) belong to \(M\). \(M\) is called a monopoly in \(G\) if every vertex \(v\in V\) is controlled by \(M\). For a specified \(M\) and a given range for edge set \(E(E_{1} \subseteq E \subseteq E_{2})\), we try to determine an \(E\) such that \(M\) is a monopoly in \(G=(V,E)\). We first present a polynomial algorithm for testing if such an \(E\) exists, by formulating it as a network flow problem. Assuming that a solution for \(E\) does exist, we then show that solutions with the maximum and minimum \(E\), respectively, can be found in polynomial time, by solving weighted matching problems. In case there is no solution for \(E\), we want to maximize the number of vertices controlled by the given \(M\). Unfortunately, this problem turns out to be NP-hard. We, therefore, design a simple approximation algorithm which guarantees an approximation ratio of 2. Cited in 3 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science Keywords:monopoly; weighted matching problems PDFBibTeX XMLCite \textit{K. Makino} et al., Algorithmica 34, No. 3, 240--260 (2002; Zbl 1016.68057) Full Text: DOI