Minimum Vertex Cut with Reachable Set (MVCRS) Problem for Suppressing Botnet Propagation in IoT Networks: Complexity and Algorithms
Sensors · 09.04.2026 · 26 (8) · 2324
DOI: 10.3390/s26082324 ↗Kurz gefasst
Fachartikel in der Zeitschrift Sensors, online erschienen am 09.04.2026. Verfasst von Shingo Yamaguchi. Beteiligte Einrichtung: Graduate School of Sciences and Technology for Innovation, Yamaguchi University, Ube 755-8611, Japan. Die Arbeit nennt 31 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Japan Society for the Promotion of Science.
Abstract (Originalsprache)
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.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Graduate School of Sciences and Technology for Innovation, Yamaguchi University, Ube 755-8611, Japan.
ORCID-Profile: Shingo Yamaguchi
Förderung
- Japan Society for the Promotion of Science
Zitieren
APA
Yamaguchi, S. (2026). Minimum Vertex Cut with Reachable Set (MVCRS) Problem for Suppressing Botnet Propagation in IoT Networks: Complexity and Algorithms. Sensors, 26(8), 2324. https://doi.org/10.3390/s26082324
Vancouver
Yamaguchi S. Minimum Vertex Cut with Reachable Set (MVCRS) Problem for Suppressing Botnet Propagation in IoT Networks: Complexity and Algorithms. Sensors. 2026;26(8):2324. doi:10.3390/s26082324
BibTeX
@article{Yamaguchi2026,
author = {Yamaguchi, Shingo},
title = {Minimum Vertex Cut with Reachable Set (MVCRS) Problem for Suppressing Botnet Propagation in IoT Networks: Complexity and Algorithms},
journal = {Sensors},
year = {2026},
volume = {26},
number = {8},
pages = {2324},
doi = {10.3390/s26082324}
}
EUVIMED