Optimal attack and reinforcement of a network

TLDR

In a nonnegative edge‑weighted network, edge weights represent the effort required to destroy an edge, while an attacker gains a benefit for each new component created by such deletions. The study defines the network’s strength as the minimal difference (or ratio) between the attacker’s effort and the benefit gained when selecting edges to destroy. Efficient algorithms are presented for computing the optimal attack, determining the network strength, and finding a minimum‑cost reinforcement to achieve a desired strength, and analogous solutions are provided for a model where the attacker isolates vertices from a fixed central vertex.

Abstract

In a nonnegative edge-weighted network, the weight of an edge represents the effort required by an attacker to destroy the edge, and the attacker derives a benefit for each new component created by destroying edges. The attacker may want to minimize over subsets of edges the difference between (or the ratio of) the effort incurred and the benefit received. This idea leads to the definition of the “strength” of the network, a measure of the resistance of the network to such attacks. Efficient algorithms for the optimal attack problem, the problem of computing the strength, and the problem of finding a minimum cost “reinforcement” to achieve a desired strength are given. These problems are also solved for a different model, in which the attacker wants to separate vertices from a fixed central vertex.