Abstract (EN)

Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant λ amounts to the NP-hard problem of finding a partial subgraph with maximum number of edges and spectral radius bounded above by λ. A software-defined network (SDN) capable of real-time topology reconfiguration can then use an algorithm for finding such subgraph to quickly remove spreading malware threats without deploying specific security countermeasures. In this paper, we propose a novel randomized approximation algorithm based on the relaxation and rounding framework that achieves a O(logn) approximation in the case of finding a subgraph with spectral radius bounded by λ∈(logn,λ1(G)) where λ1(G) is the spectral radius of the input graph and n its number of nodes. We combine this algorithm with a maximum matching algorithm to obtain a O(log2n) approximation algorithm for all values of λ. We also describe how the mathematical programming formulation we give has several advantages over previous approaches which attempted at finding a subgraph with minimum spectral radius given an edge removal budget.