Abstract In recent years, the smart city has gained large traction in government, academia, and business. Many real-world applications of smart cities can be formed to a topology graph and to optimally select a specified number of vertices to minimize the uncovered part of the topology graph. An example application is the optimal installation of a specified number of monitors at the crossroads of a city. Such a minimization problem is named a topology coverage optimization problem (TCOP) in this study, and it is a single-objective optimization problem (SOP). However, in actual situations, determining such a specific number a priori is usually difficult; instead, multiple numbers would be provided to us by the decision-makers and the minimum objective value, as well as the optimal installation solution about each number, is solicited from us—such a TCOP about multiple numbers is referred to as ”topology coverage assessment problem (TCAP)”. Hence, the TCAP consists of a series of SOPs (i.e., a series of TCOPs) each of which is NP-hard to optimize. This study introduces a multi-objective approach that is able to optimize all these TCOPs simultaneously—it is capable of obtaining high-quality results about all given numbers at the same time. Besides the simultaneous problem-solving ability, our approach, namely MoCover, also statistically significantly improved the objective value about each provided number, particularly, the vertex cover number result, because of the mutual-promoting relations between the TCOPs and the exploitation of the relations during the optimization process. In this paper, the generalization of MoCover to a class of similar problems is also introduced and discussed.