ContactPerson: rc27@cse.buffalo.edu
Remote host: ub-vpn-245-116.cc.buffalo.edu
### Begin Citation ### Do not delete this line ###
%R 2005-05
%U /tmp/2005-05.pdf
%A Chinchani, Ramkumar
%A Ha, Duc
%A Iyer, Anusha
%A Ngo, Hung Q.
%A Upadhyaya, Shambhu
%T On The Hardness of Approximating the Min-Hack Problem
%D March 02, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Inapproximability, Computer Security
%X We study the hardness of approximation for the MINIMUM HACKING problem, which roughly
can be described as the problem of finding the best way to compromise some target nodes
given a few initial compromised nodes in a network. We give three reductions to show
that MINIMUM HACKING problem is not approximable to within 2^((logn)^(1-\delta)) where
\delta = 1-1/(loglog^c(n)), for any c < 1/2. In particular, the reductions are from a
PCP, from the MINIMUM LABEL-COVER problem, and from the MINIMUM MONOTONE SATISFYING
ASSIGNMENT problem. We also analyze some heuristics on this problem.