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.
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 .
@cite_1 @cite_19 @cite_16 @cite_4
2150516767 2007385254 2054560566 2952056253
We use random sampling as a tool for solving undirected graph problems. We show that the sparse graph, or skeleton, that arises when we randomly sample a graph's edges will accurately approximate the value of all cuts in the original graph with high probability. This makes sampling effective for problems involving cuts in graphs. We present fast randomized (Monte Carlo and Las Vegas) algorithms for approximating and exactly finding minimum cuts and maximum flows in unweighted, undirected graphs. Our cut-approximation algorithms extend unchanged to weighted graphs while our weighted-graph flow algorithms are somewhat slower. Our approach gives a general paradigm with potential applications to any packing problem. It has since been used in a near-linear time algorithm for finding minimum cuts, as well as faster cut and flow algorithms. Our sampling theorems also yield faster algorithms for several other cut-based problems, including approximating the best balanced cut of a graph, finding a k-connected orientation of a 2k-connected graph, and finding integral multicommodity flows in graphs with a great deal of excess capacity. Our methods also improve the efficiency of some parallel cut and flow algorithms. Our methods also apply to the network design problem, where we wish to build a network satisfying certain connectivity requirements between vertices. We can purchase edges of various costs and wish to satisfy the requirements at minimum total cost. Since our sampling theorems apply even when the sampling probabilities are different for different edges, we can apply randomized rounding to solve network design problems. This gives approximation algorithms that guarantee much better approximations than previous algorithms whenever the minimum connectivity requirement is large. As a particular example, we improve the best approximation bound for the minimum k-connected subgraph problem from 1.85 to [math not displayed]. 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. Extracting dense subgraphs from large graphs is a key primitive in a variety of graph mining applications, ranging from mining social networks and the Web graph to bioinformatics [41]. In this paper we focus on a family of poly-time solvable formulations, known as the k-clique densest subgraph problem (k-Clique-DSP) [57]. When k=2, the problem becomes the well-known densest subgraph problem (DSP) [22, 31, 33, 39]. Our main contribution is a sampling scheme that gives densest subgraph sparsifier, yielding a randomized algorithm that produces high-quality approximations while providing significant speedups and improved space complexity. We also extend this family of formulations to bipartite graphs by introducing the (p,q)-biclique densest subgraph problem ((p,q)-Biclique-DSP), and devise an exact algorithm that can treat both clique and biclique densities in a unified way. As an example of performance, our sparsifying algorithm extracts the 5-clique densest subgraph --which is a large-near clique on 62 vertices-- from a large collaboration network. Our algorithm achieves 100 accuracy over five runs, while achieving an average speedup factor of over 10,000. Specifically, we reduce the running time from ∼2 107 seconds to an average running time of 0.15 seconds. We also use our methods to study how the k-clique densest subgraphs change as a function of time in time-evolving networks for various small values of k. We observe significant deviations between the experimental findings on real-world networks and stochastic Kronecker graphs, a random graph model that mimics real-world networks in certain aspects. We believe that our work is a significant advance in routines with rigorous theoretical guarantees for scalable extraction of large near-cliques from networks. We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any @math , given cost and demand graphs with edge weights @math respectively, we can find a set @math with @math at most @math times the optimal non-uniform sparsest cut value, in time @math provided @math . Here @math is the @math 'th smallest generalized eigenvalue of the Laplacian matrices of cost and demand graphs; @math (resp. @math ) is the weight of edges crossing the @math cut in cost (resp. demand) graph and @math is the sparsity of the optimal cut. In words, we show that the non-uniform sparsest cut problem is easy when the generalized spectrum grows moderately fast. To the best of our knowledge, there were no results based on higher order spectra for non-uniform sparsest cut prior to this work. Even for uniform sparsest cut, the quantitative aspects of our result are somewhat stronger than previous methods. Similar results hold for other expansion measures like edge expansion, normalized cut, and conductance, with the @math 'th smallest eigenvalue of the normalized Laplacian playing the role of @math in the latter two cases. Our proof is based on an l1-embedding of vectors from a semi-definite program from the Lasserre hierarchy. The embedded vectors are then rounded to a cut using standard threshold rounding. We hope that the ideas connecting @math -embeddings to Lasserre SDPs will find other applications. Another aspect of the analysis is the adaptation of the column selection paradigm from our earlier work on rounding Lasserre SDPs [GS11] to pick a set of edges rather than vertices. This feature is important in order to extend the algorithms to non-uniform sparsest cut.