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

Area of Science:

• Cybersecurity
• Network Science
• Optimization Theory

Background:

• Botnet propagation poses a significant threat to networked systems, particularly the Internet of Things (IoT).
• Effective mitigation strategies require optimal resource allocation for damage control.
• Existing heuristic approaches often fail to identify critical network vulnerabilities.

Purpose of the Study:

• To formulate the Minimum Vertex Cut with Reachable Set (MVCRS) problem as an optimization framework.
• To analyze the computational complexity and develop algorithmic solutions for MVCRS.
• To establish a theoretical baseline for optimal resource allocation in cybersecurity for botnet suppression.

Main Methods:

• Defining the MVCRS problem to minimize resource deployment cost and propagation scope.
• Demonstrating the NP-completeness of the constrained MVCRS problem.
• Reducing the fundamental trade-off optimization model to the maximum flow-minimum cut problem for polynomial-time solvability.

Main Results:

• The fundamental MVCRS optimization model is solvable in polynomial time.
• Conventional heuristics, like degree-based greedy algorithms, exhibit significant optimality gaps (up to 72.6%) in community-structured networks.
• The proposed exact algorithm achieves optimal minimum cost (0% gap) with high stability and scales efficiently for large IoT networks.

Conclusions:

• The MVCRS optimization framework provides a theoretically sound and practically efficient foundation for botnet suppression.
• The exact algorithm offers a reliable solution for optimal resource allocation in complex, real-world networked systems.
• This work highlights the limitations of heuristics and the importance of exact algorithms for critical cybersecurity challenges.