On Percolation and $NP$-Hardness

Abstract

We consider the robustness of computational hardness of problems whose input is obtained by applying independent random deletions to worst-case instances. For some classical $NP$-hard problems on graphs, such as Coloring, Vertex-Cover, and Hamiltonicity, we examine the complexity of these problems when edges (or vertices) of an arbitrary graph are deleted independently with probability $1-p>0$. We prove that for $n$-vertex graphs, these problems remain as hard as in the worst-case, as long as $p>\frac{1}{n^{1-\epsilon }}$ for arbitrary $\epsilon \in (0,1)$, unless $NP\subseteq BPP$. We also prove hardness results for Constraint Satisfaction Problems, where random deletions are applied to clauses or variables, as well as the Subset-Sum problem, where items of a given instance are deleted at random.

References in corpus (1)

• Packing, Counting and Covering Hamilton cycles in random directed graphs

Cited by in corpus (1)

• Expected Chromatic Number of Random Subgraphs