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 hardness of problems whose
inputs are obtained by applying percolation to worst-case instances.
Specifically, we show that a number of classical NP-hard graph problems
remain essentially
as hard on percolated instances as they are in the worst-case
(assuming NP $\nsubseteq$ BPP).
We also prove hardness results for other NP-hard problems
such as Constraint Satisfaction Problems and Subset Sum, with suitable
definitions of random deletions.
We focus on proving the hardness of the Maximum Independent Set problem and the
Graph Coloring problem on percolated instances.
To show this we establish the robustness
of the corresponding parameters $\alpha(\cdot)$ and $\chi(\cdot)$
to percolation, which may be of independent interest.
Given a graph $G$, let $G'$ be the graph obtained by randomly deleting edges of $G$.
We show that if $\alpha(G)$ is small, then $\alpha(G')$ remains small with probability at least $0.99$.
Similarly, we show that if $\chi(G)$ is large, then $\chi(G')$ remains large with probability at least $0.99$.
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 hardness of problems whose
inputs are obtained by applying percolation to worst-case instances.
Specifically, we show that a number of classical NP-hard graph problems
remain essentially
as hard on percolated instances as they are in the worst-case
(assuming NP $\nsubseteq$ BPP).
We also prove hardness results for other NP-hard problems
such as Constraint Satisfaction Problems and Subset Sum, with suitable
definitions of random deletions.
We focus on proving the hardness of the Maximum Independent Set problem and the
Graph Coloring problem on percolated instances.
To show this we establish the robustness
of the corresponding parameters $\alpha(\cdot)$ and $\chi(\cdot)$
to percolation, which may be of independent interest.
Given a graph $G$, let $G'$ be the graph obtained by randomly deleting edges of $G$.
We show that if $\alpha(G)$ is small, then $\alpha(G')$ remains small with probability at least $0.99$.
Similarly, we show that if $\chi(G)$ is large, then $\chi(G')$ remains large with probability at least $0.99$.
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.
