EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Shingo Yamaguchi iD

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

IoT securitybotnet containmentcomputational complexitydiffusion controlmaximum flow minimum cut theoremnetwork resiliencereachable set optimization

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}
}
Kostenlos starten →