Towards minimizing the R metric for measuring network robustness

With the prevalence of cyber-attacks on infrastructure networks such as the Internet backbone, measuring the robustness of network topologies has become a critical issue. To this end, a metric called '$R$' has been proposed and widely used. '$R$' assumes that an attack on a network consists of $n$ rounds of node removals with one node removed each round, where $n$ is the number of nodes in the network. Since the value of $R$ depends on the sequence of node removals, finding the sequence minimizing $R$ becomes an interesting problem, denoted as Min-R hereafter. Although many heuristic approaches have been proposed for Min-R, there has been no optimal polynomial-time algorithm given so far, nor is Min-R proved NP-hard. To fill this gap, this paper presents the following fundamental results. First, to minimize $R$, a node needs to be always removed from the largest connected component of the current network in each round. Second, the Min-R problem has an Optimal Substructure, which allows it to be solved by Dynamic Programming in exponential time instead of the naive factorial time on general graphs. Finally, an efficient and optimal logarithmic-time algorithm is given for Min-R on path graphs, with its complexity and optimality proved.