On percolation and ‐hardness
Huck Bennett, Daniel Reichman, Igor Shinkar · Random Structures and Algorithms · 2018
Abstract The edge‐percolation and vertex‐percolation random graph models start with an arbitrary graphG, and randomly delete edges or vertices ofGwith some fixed probability. We study the computational complexity of problems whose inputs are obtained by applying percolation to worst‐case instances. Specifically, we show that a number of classical ‐hard problems on graphs remain essentially as hard on percolated instances as they are in the worst‐case (assuming ). We also prove hardness results for other ‐hard problems such as Constraint Satisfaction Problems and Subset‐Sum, with suitable definitions of random deletions. Along the way, we establish that foranygiven graphGthe independence number and the chromatic number are robust to percolation in the following sense. Given a graphG, let be the graph obtained by randomly deleting edges ofGwith some probability . We show that if is small, then remains small with probability at least 0.99. Similarly, we show that if is large, then remains large with probability at least 0.99. We believe these results are of independent interest.