On the Hardness of Approximating the Min-Hack Problem

Several reductions are given to show that Minimum Hacking is not approximable to within 2^{(\log n)^{1-\delta}} where δ = 1−$$\frac{1}{{log}{log}}$$cn, for any c < 1/2.

Abstract

Abstract We show several hardness results for the Minimum Hacking problem, which roughly can be described as the problem of finding the best way to compromise a target node given a few initial compromised nodes in a network. We give several reductions to show that Minimum Hacking is not approximable to within $$2^{(\log n)^{1-\delta}}$$ where δ = 1− $$\frac{1}{{log}{log}}$$ c n, for any c