A Note on the Computational Complexity of Unsmoothened Vertex Attack Tolerance

Abstract

We have previously introduced vertex attack tolerance (VAT) and unsmoothened VAT (UVAT), denoted respectively as $\tau (G)={\min }_{S\subset V}\frac{|S|}{|V-S-C_{max}(V-S)|+1}$ and $\hat{\tau }(G)={\min }_{S\subset V}\frac{|S|}{|V-S-C_{max}(V-S)|}$, where $C_{max}(V-S)$ is the largest connected component in $V-S$, as appropriate mathematical measures of resilience in the face of targeted node attacks for arbitrary degree networks. Here we prove the hardness of approximating $\hat{\tau }$ under various plausible computational complexity hypotheses.