Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR15-132 | 15th July 2016 00:13

On Percolation and NP-Hardness

RSS-Feed




Revision #2
Authors: Daniel Reichman, Igor Shinkar, Huck Bennett
Accepted on: 15th July 2016 00:13
Downloads: 262
Keywords: 


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 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$.


Revision #1 to TR15-132 | 15th July 2016 00:06

On Percolation and NP-Hardness





Revision #1
Authors: Daniel Reichman, Igor Shinkar
Accepted on: 15th July 2016 00:06
Downloads: 162
Keywords: 


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 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$.


Paper:

TR15-132 | 13th August 2015 18:30

On Percolation and NP-Hardness





TR15-132
Authors: Daniel Reichman, Igor Shinkar
Publication: 15th August 2015 15:17
Downloads: 607
Keywords: 


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.



ISSN 1433-8092 | Imprint