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 @math -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 @math . We prove that for @math -vertex graphs, these problems remain as hard as in the worst-case, as long as @math for arbitrary @math , unless @math . 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.
When @math is sufficiently small, algorithms for random graphs and random formulas can be proven to find the optimal solution (with high probability) for percolated instance. For example, for graph coloring, it is known that for @math with some positive constant @math , with high probability @math is @math -degenerate, and hence can be 3-colored in polynomial time @cite_2 . Since the property of being 2-degenerate is monotone, and as @math -colorability can be decided in polynomial time, it follows that for every @math -vertex graph and @math , one can find in polynomial time with high probability a coloring of the edge percolated graph with the minimum number of colors.
@cite_2
2048267719
Let G3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of vertices of distinct color classes, randomly and independently, to be edges with probability p. We describe a polynomial-time algorithm that finds a proper 3-coloring of G3n,p,3 with high probability, whenever p @math c n, where c is a sufficiently large absolute constant. This settles a problem of Blum and Spencer, who asked if an algorithm can be designed that works almost surely for p @math polylog(n) n [J. Algorithms, 19 (1995), pp. 204--234]. The algorithm can be extended to produce optimal k-colorings of random k-colorable graphs in a similar model as well as in various related models. Implementation results show that the algorithm performs very well in practice even for moderate values of c.