Revision #2 Authors: Daniel Reichman, Igor Shinkar, Huck Bennett

Accepted on: 15th July 2016 00:13

Downloads: 1368

Keywords:

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 Authors: Daniel Reichman, Igor Shinkar

Accepted on: 15th July 2016 00:06

Downloads: 817

Keywords:

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

TR15-132 Authors: Daniel Reichman, Igor Shinkar

Publication: 15th August 2015 15:17

Downloads: 1470

Keywords:

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.