On percolation and NP‐hardness. Issue 2 (30th March 2018) - Bennett, Huck; Reichman, Daniel; Shinkar, Igor
Abstract: The edge‐percolation and vertex‐percolation random graph models start with an arbitrary graph G, and randomly delete edges or vertices of G with 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 N P ‐hard problems on graphs remain essentially as hard on percolated instances as they are in the worst‐case (assuming N P ⊈ B P P ). We also prove hardness results for other N P ‐hard problems such as Constraint Satisfaction Problems and Subset‐Sum, with suitable definitions of random deletions. Along the way, we establish that for any given graph G the independence number α ( G ) and the chromatic number χ ( G ) are robust to percolation in the following sense. Given a graph G, let G ′ be the graph obtained by randomly deleting edges of G with some probability p ∈ ( 0, 1 ) . We show that if α ( G ) is small, then α ( G ′ ) remains small with probability at least 0.99. Similarly, we show that if χ ( G ) is large, then χ ( G ′ ) remains large with probability at least 0.99. We believe these results are of independent interest.