text: 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.
  @cite_1: Abstract Given a graph G and an ordering p of its vertices, denote by A ( G , p ) the number of colors used by the greedy coloring algorithm when applied to G with vertices ordered by p . Let e, ϑ, Δ be positive constants. It is proved that for each n there is a graph G n such that the chromatic number of G n is at most n e , but the probability that A(G n , p) (1 − ϑ)n log 2 n for a randomly chosen ordering p is O ( n − Δ ).
  @cite_19: We initiate a study of when the value of mathematical relaxations such as linear and semi-definite programs for constraint satisfaction problems (CSPs) is approximately preserved when restricting the instance to a sub-instance induced by a small random subsample of the variables. Let C be a family of CSPs such as 3SAT, Max-Cut, etc., and let Π be a mathematical program that is a relaxation for C, in the sense that for every instance P ∈ C, Π(P) is a number in [0, 1] upper bounding the maximum fraction of satisfiable constraints of P. Loosely speaking, we say that subsampling holds for C and Π if for every sufficiently dense instance P ∈ C and every e > 0, if we let P' be the instance obtained by restricting P to a sufficiently large constant number of variables, then Π(P') ∈ (1 ± e)Π(P). We say that weak subsampling holds if the above guarantee is replaced with Π(P') = 1 − θ(γ) whenever Π(P) = 1 − γ, where θ hides only absolute constants. We obtain both positive and negative results, showing that: 1. Subsampling holds for the BasicLP and BasicSDP programs. BasicSDP is a variant of the semi-definite program considered by Raghavendra (2008), who showed it gives an optimal approximation factor for every constraint-satisfaction problem under the unique games conjecture. BasicLP is the linear programming analog of BasicSDP. 2. For tighter versions of BasicSDP obtained by adding additional constraints from the Lasserre hierarchy, weak subsampling holds for CSPs of unique games type. 3. There are non-unique CSPs for which even weak subsampling fails for the above tighter semi-definite programs. Also there are unique CSPs for which (even weak) subsampling fails for the Sherali-Adams linear programming hierarchy. As a corollary of our weak subsampling for strong semi-definite programs, we obtain a polynomial-time algorithm to certify that random geometric graphs (of the type considered by Feige and Schechtman, 2002) of max-cut value 1 − γ have a cut value at most 1 − γ 10. More generally, our results give an approach to obtaining average-case algorithms for CSPs using semi-definite programming hierarchies.
  @cite_16: 
  @cite_4: The notion of recoverable value was advocated in the work of Feige, Immorlica, Mirrokni and Nazerzadeh (APPROX 2009) as a measure of quality for approximation algorithms. There, this concept was applied to facility location problems. In the current work we apply a similar framework to the maximum independent set problem (MIS). We say that an approximation algorithm has recoverable factor ρ, if for every graph it recovers an independent set of size at least where d(v) is the degree of vertex v, and I ranges over all independent sets in G. Hence, in a sense, from every vertex v in the maximum independent set the algorithm recovers a value of at least toward the solution. This quality measure is most effective in graphs in which the maximum independent set is composed of low degree vertices. A simple greedy algorithm achieves . We design a new randomized algorithm for MIS that ensures an expected recoverable factor of at least . In passing, we prove that approximating MIS in graphs with a given k-coloring within a ratio larger than 2 k is unique-games hard. This rules out an alternative approach for obtaining . © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 142–159, 2015
summary: Randomly subsampling subgraphs by including each edge independently in the sample with probability @math has been studied extensively in works concerned with cuts and flows (e.g., @cite_16 ). More recently, sampling subgraphs has been used to find independent sets @cite_4 (the main sampling technique used, e.g., the layers model is not independent-it introduces dependencies between sampled vertices). The effect of subsampling variables in mathematical relaxations of constraint satisfaction problems on the value of these relaxations was studied in @cite_19 . Edge-percolated graphs have been also used to construct hard-instance for specific algorithms. For example, @cite_1 proved that the well known greedy coloring algorithm performs poorly on the complete @math -partite graph in which every edge is removed independently with probability @math and @math for @math . Namely, for this graph @math , even if vertices are considered in a random order by the greedy algorithm, with high probability @math colors are used to color the percolated graph whereas @math .