On percolation and NP‐hardness. Issue 2 (30th March 2018)

• Record Type: Journal Article
• Authors: Bennett, Huck; Reichman, Daniel; Shinkar, Igor
• Is Part Of: Random structures & algorithms. Volume 54:Issue 2(2019)
• Page Start: 228
• Page End: 257
• Publication Date: 2018-03-30
• Subjects: chromatic number -- hardness of approximation -- independence number -- percolation -- random subgraphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20772
• Languages: English
• ISSNs: 1042-9832

Abstract

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.