Identifying Critical Fortification Node Sets for Directed Service Paths via Minimum Node-Cut Optimization

Maintaining end-to-end connectivity under disruption is a central problem in systems resilience. This study examines how limited protection resources can increase the minimum node-removal cost required to disconnect a specified service. Mission-Path Cut Fortification (MPCF) models a directed service as a functional graph and treats protection as a finite increase in node-removal cost. Node splitting yields a compact mixed-integer linear program, and an independent cut-generation formulation verifies its optimal value. On 45 synthetic graphs, mean minimum-cut values are 33.62 for MPCF-Exact and MPCF-CG, 32.30 for MPCF-Greedy, 30.41 for PathFrequency, and 27.38 without fortification. Graph-level analyses treat budgets as repeated measurements, and a 90-graph extension reproduces the paired effects for the nine designated methods. Further experiments assess heterogeneous fortification costs and effectiveness. Scaling to 1000 nodes identifies the computational limits of both exact formulations through stopping times and optimality bounds. Ten source–sink cases from public transport and telecommunications networks demonstrate applicability to empirical path topologies. Partial-capacity analysis shows that complete-disconnection and residual-capacity criteria can favor different fortification sets. The findings support joint node-set selection for resistance to complete disconnection and show that the service criterion should be specified before resources are allocated.