Given a graph G = (V, E) and a set of vertices MV, a vertex v ∈ V is said to be controlled by M if the majority of v’s neighbors (including itself) belongs to M. M is called a monopoly if every vertex v ∈ V is controlled by M. For a specified M and a range for E (E1 EE2),we try to determine 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 E does exist, we then show that a solution with the maximum or minimum |E| can be found in polynomial time, by considering them as weighted matching problems.