Minimum Vertex Cut with Reachable Set (MVCRS) Problem for Suppressing Botnet Propagation in IoT Networks: Complexity...

This paper formulates the "Minimum Vertex Cut with Reachable Set" (MVCRS) problem as an optimization framework to suppress botnet propagation in networked systems, and clarifies its computational complexity and algorithmic solutions. Building a firewall to minimize damage is essential for addressing botnet propagation in Internet of Things (IoT) networks. We define the basic MVCRS problem as minimizing the sum of the weight of the deployed resources and the resulting propagation scope. While we demonstrate that the constrained version of the problem is NP-complete, we show that the fundamental trade-off optimization model can be solved in polynomial time by reducing it to the maximum flow-minimum cut problem. This provides a theoretical baseline for optimal resource allocation in cybersecurity. Experimental evaluations reveal the limitations of conventional heuristics. In community-structured networks, the degree-based greedy algorithm overlooks critical bridge nodes, yielding an optimality gap of up to 72.6% above the theoretical minimum cost. Conversely, our exact algorithm consistently guarantees the optimal minimum cost (a 0% gap) with high statistical stability across diverse topologies. Furthermore, it scales efficiently to solve 100,000-node IoT networks within practical time limits, proving to be a reliable and efficient foundation for botnet suppression in complex real-world systems.