On percolation and ‐hardness
On percolation and ‐hardness
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 …